Kod Prufera

laki_me · Post autor: **laki_me** » 23 wrz 2009, o 16:27

Witam

Jako że zbliżają się poprawki ... mam problem z kodem Prufera, znam algorytm do wyznaczania drzewa na podstawie kodu Prufera ale w sytuacji kiedy w tym kodzie występują 2 liczby, a jeśli kod jest następujący:
(1,3,5,7,9,5,1) to wtedy po przejściu całego algorytmu zostaje mi więcej niż ostatnia krawędź, a i jeszcze przy tym zadaniu jest informacja że jest to drzewo oznakowane.

Dumel · Post autor: **Dumel** » 23 wrz 2009, o 18:12

to nabazgrane po prawej na górze to 8

laki_me · Post autor: **laki_me** » 23 wrz 2009, o 21:06

przedstaw tok rozumowania, bo idąc podstawowym kodem Prufera to będzie wyglądało tak
1 3 5 7 9 5 1
1 2 3 4 5 6 7 8 9

i tak 1 opuszczamy idzie 2-1 trzy opuszczamy idzie 4-3 5 opuszczamy idzie 6-5 7 opuszczamy idzie 8-7 ... itd. no tyle że po usunięciu powinny mi zostać 2 wartości na dolnej tabeli a zostaje 7

Dumel · Post autor: **Dumel** » 24 wrz 2009, o 10:52

ok, więc opisze kolejno ruchy przy czym pierwszy wiersz to "nieprzerobiona" część kodu, drugi to niewykreślone wierzchołki a trzeci to krawędź którą rysujemy

1357951
123456789
2-1

357951
13456789
4-3

57951
1356789
5-3

7951
156789
7-6

951
15789
9-7

51
1589
5-8

1
159
1-5

(brak)
19
1-9

laki_me · Post autor: **laki_me** » 24 wrz 2009, o 11:18

Serdeczne dzięki, zrozumiałem teraz, kurcze przecież to takie proste