Stopień minimalny

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Kate2410
Użytkownik
Użytkownik
Posty: 38
Rejestracja: 17 lis 2019, o 22:09
Płeć: Kobieta
wiek: 20
Podziękował: 3 razy

Stopień minimalny

Post autor: Kate2410 » 22 mar 2020, o 09:30

Niech \(\displaystyle{ G=(X,Y;E)}\) będzie grafem dwudzielnym. Wykaż, że jeżeli \(\displaystyle{ \delta(G) \ge |X|2}\), to:

a) minimalny zbiór pokrywający w \(\displaystyle{ G}\) ma \(\displaystyle{ |X|}\) wierzchołków,

b) maksymalny zbiór niezależny w \(\displaystyle{ G}\) ma \(\displaystyle{ |Y|}\) wierzchołków.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

ODPOWIEDZ