Strona 1 z 1

Drzewo na kod Prufera i na odwrót

: 26 maja 2014, o 16:03
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.