Drzewo na kod Prufera i na odwrót

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
pitexor
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 6 lis 2013, o 20:37
Płeć: Mężczyzna
Lokalizacja: Poland
Podziękował: 7 razy

Drzewo na kod Prufera i na odwrót

Post autor: pitexor »

Witam otóż mam takie drzewo:

Chciałbym wyznaczyć kod Prufera z niego, wg. sposobu co jest na wikipedii:

Wychodzi mi taki (4,2,7,5,6,4) . Pierwsze usuwam krawędź (3-4 ) potem pojawia się problem bo wszystkie wierzchołki mają stopień równy 2 . To usuwam (1-2) potem (1-7) , (2 -5) , (5-6) , (6,4) i zostaje jedna krawędź (4-7) i otrzymuję taki oto kod: (4.2,7,5,6,4) i tu problem bo otrzymuje kod który ma 6 elementów to znaczy że drzewo ma 8 wierzchołków, a u mnie ma 7 ( więc kod powinien mieć 5 elementów ?) To znaczy że kod nie działa dla grafu z nieparzystą ilością wierzchołków ? Używam tego sposobu z wikipedii.
Po poskładaniu kodu prufera na drzewo dostaję takie:
[url]http://imgur.com/Zlq9X7p[/url]

Proszę o pomoc.


Sprawa Wyjaśniona : To nie jjest drzewo bo ma cykl.
ODPOWIEDZ