graf, zbiór pokrywajacy, niezależny

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
aGabi94
Witam na forum
Witam na forum
Posty: 6
Rejestracja: 04 mar 2014, 13:17
Podziękowania: 1 raz
Płeć:

graf, zbiór pokrywajacy, niezależny

Post autor: aGabi94 » 16 mar 2015, 22:36

Wykaż,że jeśli \(\delta(G) \geq \frac{|X|}{2}\) to :
a) minimalny zbiór pokrywajacy w G ma |X| wierzchołków
b) maksymalny zbiór niezależny w G ma |Y| wierzchołków