Kod Prufera

0Mniac · Post autor: **0Mniac** » 14 cze 2015, o 14:13

Witam. Mam taki kod Prufera: 3423423. Mógłby mi ktoś objaśnić jak z tego "wyciągnąć" drzewo?

EDIT:

Rozpisałem to sobie tak:

Na górze ciąg \(\displaystyle{ 123456789}\) bo +2 do ilości liczb w kodzie Prufera
Na dole ciąg \(\displaystyle{ 3423423}\)

I teraz biorę 1, nie ma go na dole więc \(\displaystyle{ 1-3}\)
Wykreślam 1 i 3 więc jest

\(\displaystyle{ 23456789}\)
\(\displaystyle{ 423423}\)

Biorę 2- jest na dole, czyli nic nie działam z tym, biorę 3 to samo, 4 to samo.
biorę 5, nie ma go na dole więc wykreślam z 4 i mam \(\displaystyle{ 5-4}\)

\(\displaystyle{ 2346789}\)
\(\displaystyle{ 23423}\)

To samo z 6, 7 i 8, czyli \(\displaystyle{ 6-2}\), dalej \(\displaystyle{ 7-3}\) oraz \(\displaystyle{ 8-4}\). Zostaje mi:

\(\displaystyle{ 2349}\)
\(\displaystyle{ 23}\)

I teraz nie wiem czy powinienem brać 9, moim tokiem rozumowania tak, ale znajomy rozwiązał to inaczej. Co robić teraz?

EDIT2:

Kumpel mi tylko rozwiązanie podał, wnioskując z tego co napisał to biorę teraz ostatnie połączenie jest \(\displaystyle{ 8-4}\), więc biorę 4 i patrzę, nie ma go na dole więc wykreślam z 2 mając kolejne \(\displaystyle{ 4-2}\)

\(\displaystyle{ 239}\)
\(\displaystyle{ 3}\)

Teraz biorę ostatnie połączenie czyli \(\displaystyle{ 4-2}\), czyli 2 i sprawdzam, nie ma na dole czyli mam \(\displaystyle{ 2-3}\)

Zostaje:

\(\displaystyle{ 39}\)

Nie ma nic na dole więc łącze od końca \(\displaystyle{ 9-3}\)

Wychodzi więc \(\displaystyle{ 1-3,5-4,6-2,7-3,8-4,4-2,2-3,9-3}\). Narysować umiem. Pytanie- dobry sposób rozumowania i rozwiązanie?

roskuwaczus · Post autor: **roskuwaczus** » 14 cze 2015, o 17:05

Dobry wynik i po drugiej edycji jest wszystko dobrze (kolos w poniedziałek ?)

0Mniac · Post autor: **0Mniac** » 14 cze 2015, o 17:19

Dokładnie

Barbara777 · Post autor: **Barbara777** » 14 cze 2015, o 17:25

Mnie wyszlo \(\displaystyle{ 1-3, 5-4, 6-2, 7-3, 8-4, 9-2, 2-3, 3-4}\)
Sprawdzilam tak: narysowalam drzewo na podstawie danych powyzej, a potem napisalam odpowiadajacy mu kod Prüfera (bo tak najprosciej) - zgadza sie. Natomiast nie zgadza sie z kodem twojego kumpla.

roskuwaczus · Post autor: **roskuwaczus** » 14 cze 2015, o 18:08

Barbara777 pisze:Mnie wyszlo \(\displaystyle{ 1-3, 5-4, 6-2, 7-3, 8-4, 9-2, 2-3, 3-4}\)
Sprawdzilam tak: narysowalam drzewo na podstawie danych powyzej, a potem napisalam odpowiadajacy mu kod Prüfera (bo tak najprosciej) - zgadza sie. Natomiast nie zgadza sie z kodem twojego kumpla.

Wydaje mi się że pomyliłaś się przy końcu ty masz 3423432 a powinno być 3423423