Drzewo izomorficzne ze swoim dopełnieniem

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Wojtuce
Użytkownik
Użytkownik
Posty: 24
Rejestracja: 12 maja 2014, o 11:47
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 3 razy

Drzewo izomorficzne ze swoim dopełnieniem

Post autor: Wojtuce »

Witam,

mam problem, nie wiem od czego zacząć to zadanie:
"Znajdź każde drzewo T, które jest izomorficzne ze swoim dopełnieniem"

Z góry dziękuję za pomoc
Awatar użytkownika
Santiago A
Użytkownik
Użytkownik
Posty: 248
Rejestracja: 22 sty 2016, o 20:56
Płeć: Mężczyzna
Lokalizacja: Zaragoza
Podziękował: 9 razy
Pomógł: 51 razy

Drzewo izomorficzne ze swoim dopełnieniem

Post autor: Santiago A »

Wskazówka: jeśli drzewo ma \(\displaystyle{ n}\) wierzchołków, to zarówno ono samo jak i jego dopełnienie muszą mieć \(\displaystyle{ n-1}\) krawędzi, czyli musisz rozwiązać równanie

\(\displaystyle{ {n \choose 2} - (n-1) = n-1}\),

z którego wynika \(\displaystyle{ n = 1}\) lub \(\displaystyle{ n = 4}\).
Wojtuce
Użytkownik
Użytkownik
Posty: 24
Rejestracja: 12 maja 2014, o 11:47
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 3 razy

Drzewo izomorficzne ze swoim dopełnieniem

Post autor: Wojtuce »

Rzeczywiście, przydatna obserwacja. Ale nadal nie mam pomysłu, co dalej.
Awatar użytkownika
Santiago A
Użytkownik
Użytkownik
Posty: 248
Rejestracja: 22 sty 2016, o 20:56
Płeć: Mężczyzna
Lokalizacja: Zaragoza
Podziękował: 9 razy
Pomógł: 51 razy

Drzewo izomorficzne ze swoim dopełnieniem

Post autor: Santiago A »

Narysuj wszystkie drzewa o mniej niż pięciu wierzchołkach, nie ma tego sporo.
ODPOWIEDZ