Dominowanie grafów

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Ewellka1312
Użytkownik
Użytkownik
Posty: 12
Rejestracja: 15 paź 2015, o 09:50
Płeć: Kobieta
Lokalizacja: Podkarpacie
Podziękował: 1 raz

Dominowanie grafów

Post autor: Ewellka1312 »

Czy w tym twierdzeniu zakładamy, że zbiór \(\displaystyle{ D}\) istnieje czy zbiór \(\displaystyle{ D}\) jest dowolny? I od czego zacząć aby udowodnić to twierdzenie?
Każdy spójny graf \(\displaystyle{ G}\) posiadający co najmniej dwa wierzchołki posiada zbiór dominujący \(\displaystyle{ D}\), którego dopełnienie \(\displaystyle{ {V\setminus G}}\) też jest zbiorem dominującym.
Mruczek
Użytkownik
Użytkownik
Posty: 1114
Rejestracja: 26 paź 2008, o 19:43
Płeć: Mężczyzna
Podziękował: 23 razy
Pomógł: 157 razy

Re: Dominowanie grafów

Post autor: Mruczek »

Trzeba pokazać, że istnieje taki zbiór \(\displaystyle{ D}\), wskazać go, może być to dowolny zbiór.
Hint1:    
Hint2:    
Rozwiązanie:    
ODPOWIEDZ