Izomorfizm grafu

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
darksaq
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 7 mar 2017, o 17:23
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 2 razy

Izomorfizm grafu

Post autor: darksaq »

Mam poniższe zadanie:

Narysuj kilka nie izomorficznych drzew w klice K7. Podaj kody drzew jako ciągi stopni jego wierzchołków. Uzasadnij, że drzewa o tym samym kodzie ciągów stopni nie są izomorficzne.

Narysowałem takie:
AU
AU
graf.png (2.21 KiB) Przejrzano 141 razy
1) (2,2,2,2,1,1,1)
2) (4,2,2,1,1,1,1)
3) (4,2,2,1,1,1,1)

Chciałem prosić o sprawdzenie czy w ogóle dobrze się do tego zabieram i czy graf 2) 3) mogą być jako dowód na to, że pomimo takiego samego kodu nie są izomorficzne?
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: Izomorfizm grafu

Post autor: Mruczek »

W pierwszym grafie ciąg stopni jest zły, powinno być: \(\displaystyle{ (2,2,2,2,2,1,1)}\), pozostałe są ok.
2) i 3) mogą być jako przykład na nieizomorficzne drzewa o tym samym ciągu stopni.
ODPOWIEDZ