Kod Prüfera

Drzewo oznaczone z kodem Prüfera {4,4,4,5}.

Kod Prüfera – kod pozwalający na zapisywanie drzewa (w rozumieniu teorii grafów) w formie skompresowanego ciągu (bez wypisywania całego zbioru krawędzi) długości n-2, gdzie n stanowi liczbę wierzchołków grafu.

Wyznaczanie kodu Prüfera

Algorytm wyznaczania kodu Prüfera na podstawie opisu drzewa. Z danego drzewa o zbiorze wierzchołków opisanym jako {1,2,...,n} prowadzi do kodu Prüfera stanowiącego n-2 wyrazowy ciąg liczb ze zbioru {1,2,...,n}.

1. Jeśli w drzewie jest więcej niż jedna krawędź, szukamy w drzewie wierzchołka stopnia jeden o jak najniższym numerze ze zbioru {1,2,...,n} nazwijmy go v. Znajdujemy jedynego sąsiada tego wierzchołka, nazwijmy go w.
2. Do ciągu wyjściowego dopisujemy w, usuwamy krawędź {v,w}
3. Jeśli w drzewie została więcej niż jedna krawędź to przejść ponownie do punktu pierwszego. W przeciwnym wypadku, zapisany dotychczas ciąg jest ciągiem wyjściowym.

Uwaga: Łatwo zaobserwować, że kod Prüfera można zapisać tylko dla drzew o liczbie wierzchołków większej od 2.

Wyznaczanie drzewa z kodu Prüfera

Algorytm wyznaczania opisu grafu na podstawie kodu Prüfera. Z danego kodu Prüfera stanowiącego n-2 wyrazowy ciąg liczb (a₁,a₂,...,a_n-2) ze zbioru {1,2,...,n} prowadzi do opisu drzewa o zbiorze wierzchołków {1,2,...,n} z kodem Prüfera (a₁,a₂,...,a_n-2).

1. Tworzymy dwie listy L₁=(a₁,a₂,...,a_n-2), L₂={1,2,...,n}. Drzewo zaczynamy tworzyć od grafu o wierzchołkach {1,2,...,n} i wyłącznie trywialnych składowych (pusty zbiór krawędzi). Wyznaczmy sobie liczbę c:=1.
2. Wyznaczamy w L₂ najmniejszą wartość, która nie występuje w liście L₁ nazwijmy ją i.
3. Dodajemy do drzewa krawędź {i,a_c}. Z listy L₁, usuwamy a_c. Z listy L₂, usuwamy element i.
4. Jeśli L₁ jest niepuste to definiujemy c:=c+1 i wracamy do punktu 2. W przeciwnym wypadku L₂ zawiera jeszcze dwa elementy, nazwijmy je l₁ i l₂. Do zbioru krawędzi drzewa dodajemy krawędź {l₁,l₂} i kończymy działanie algorytmu.

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Prüfer Code, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).