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.

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

Wyznaczanie kodu Prüfera

edytuj

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

edytuj

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

  1. Tworzymy dwie listy L1=(a1,a2,...,an-2), L2={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 L2 najmniejszą wartość, która nie występuje w liście L1 nazwijmy ją i.
  3. Dodajemy do drzewa krawędź {i,ac}. Z listy L1, usuwamy ac. Z listy L2, usuwamy element i.
  4. Jeśli L1 jest niepuste to definiujemy c:=c+1 i wracamy do punktu 2. W przeciwnym wypadku L2 zawiera jeszcze dwa elementy, nazwijmy je l1 i l2. Do zbioru krawędzi drzewa dodajemy krawędź {l1,l2} i kończymy działanie algorytmu.

Linki zewnętrzne

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