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
Drzewo izomorficzne ze swoim dopełnieniem
- Santiago A
- 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
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}\).
\(\displaystyle{ {n \choose 2} - (n-1) = n-1}\),
z którego wynika \(\displaystyle{ n = 1}\) lub \(\displaystyle{ n = 4}\).
-
- 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
Rzeczywiście, przydatna obserwacja. Ale nadal nie mam pomysłu, co dalej.
- Santiago A
- 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
Narysuj wszystkie drzewa o mniej niż pięciu wierzchołkach, nie ma tego sporo.