Prüfersekvens

Inom grafteori är en Prüfersekvens (eller Prüferkod) för ett märkt träd en sekvens som unikt beskriver ett givet träd. Samtidigt har varje träd en unik Prüfersekvens, varigenom Prüfersekvenser är bijektiva avbildningar av träd. Prüfersekvensen för ett (orotat) märkt träd med n noder har längden n − 2, och kan genereras med en enkel iterativ algoritm. För ett rotat märkt träd har sekvensen längden n − 1.

Prüfersekvenser användes först för att bevisa Cayleys formel av Heinz Prüfer 1918.

Några definitioner

Ett blad (löv) är en nod av ordning (antalet anslutande kanter) ett. En intern nod är en nod med ordning två eller större.

Hur man beräknar Prüfersekvensen för ett orotat märkt träd

Man kan generera Prüfersekvensen för ett orotat märkt träd genom att successivt avlägsna de lägsta (det vill säga de vars markering kommer först i den lexikografiska ordning efter vilka de märkts) bladen från trädet tills endast två återstår och ange från vilken interna nod de plockats. Märkningen av dessa interna noder och i vilken ordning de antecknas motsvarar trädets Prüfersekvens. (Notera speciellt att det bara är de från början interna noderna som finns i sekvensen - alla markeringar som inte är med i sekvensen är alltså blad i det "orörda" trädet).

Exempel1: Betrakta trädet med sex noder i första bilden ovan till vänster. Det har fyra blad (1, 2, 3 och 6) och två interna noder (4 och 5). Vi börjar med att plocka bort det lägsta bladet, 1, och antecknar att vi tog bort det från nod 4 (fyra är alltså det första talet i sekvensen). Nu, i andra bilden, är det lägsta bladet 2 och vi plockar bort det också från nod 4 (fyra blir vårt andra tal i sekvensen). I tredje bilden är det lägsta bladet 3 och vi antecknar återigen en fyra i sekvensen när vi plockar bort detta. Nu har nod fyra blivit ett blad och eftersom trädets enda andra blad, sexan, är högre så plockar vi bort blad fyra och antecknar fem som vårt fjärde och sista tal i sekvensen: 4,4,4,5. Vi behöver inte anteckna att vi kan plocka bort fem från sex, eftersom detta är de enda kvarvarande noderna i trädet och det är ju självklart att de sitter ihop. Och vi ser ju också att, eftersom sex inte ingår i Prüfersekvensen, så måste sex ha varit ett blad från början.

Tree graph Prüfer-Code

Exempel2: I trädet med sju noder ovan plockar vi bort 1 (från 5), sedan 3 (från 5), 4 (från 2), 5 (från 2) och slutligen 6 (från 2). Prüfersekvensen är för detta träd alltså 5,5,2,2,2. Att sekvensen bara innehåller femmor och tvåor talar om att alla andra noder (1, 3, 4, 6 och 7) var blad från början.

Eftersom noderna är märkta, och deras märkning är unik och ordnad, finns det alltid ett lägsta blad att plocka bort, så det är entydigt vilket blad som åker i varje omgång. Eftersom varje blad endast är anslutet till en nod är det också entydigt vilken nod som tillfogas sekvensen. Sålunda är Prüfersekvensen för varje givet orotat märkt träd unik.

En annan sak som framgår av Prüfersekvensen är nodernas grad. Antalet gånger en nod förekommer i sekvensen är ju lika med det antal gånger ett till noden förbundet blad plockas bort. När noden väl blivit ett blad, så har den graden ett. Sålunda är varje nods grad ett mer än det antal gånger den förekommer i sekvensen. I exempel 2 ovan förekommer nod 5 två gånger och har alltså grad 3, nod 2 förekommer tre gånger och har grad 4, medan övriga noder inte förekommer alls och därför har grad 1 (vilket ju stämmer helt med att de är blad "från början").

Hur man beräknar Prüfersekvensen för ett rotat märkt träd

Skillnaden mellan ett rotat och ett orotat träd är att en av trädets noder är en rot. Denna rot kan aldrig bli ett blad och således ej plockas bort. Förfaringssättet vid sekvensens skapande är i övrigt detsamma som för ett orotat träd. När man har två noder kvar (roten förbunden med ett blad) tar man bort bladet och för till roten till sekvensen. Prüfersekvensen för ett rotat träd har alltså ett element mer än det orotade trädet och dess längd är sålunda n-1.

Tree graph Prüfer-Code

Exempel: Trädet ovan (samma som i exempel 2) ger om det är orotat sekvensen 5,5,2,2,2. Om en av noderna 2 eller 7 skulle vara rot har vi i stället sekvensen 5,5,2,2,2,2 eller 5,5,2,2,2,7, där det sjätte elementet anger roten.

Notera att om någon annan nod än de "två sista i det orotade trädet" skulle vara rot kan detta påverka sekvensen mer än i sista steget. Om exempelvis nod 3 är rot blir förfaringssättet sålunda: Ta bort 1 (från 5), ta bort 4 (från 2), ta bort 6 (från 2), ta bort 7 (från 2), ta bort 2 (från 5) och ta bort 5 (från roten 3). I andra steget kan inte nod 3 tas bort från nod 5, eftersom den ju är rot, och då får vi ta nod 4 från nod 2, etcetera, i stället. Sekvensen blir med nod 3 som rot sålunda 5,2,2,2,5,3.

Hur man återskapar ett orotat märkt träd från dess Prüfersekvens

Att Prüfersekvensen endast innehåller noder som är interna i det fulla trädet är självklart, inga ursprungliga blad kan ju bli noterade. Att den innehåller alla interna noder ses enkelt av att när man är klar, har man två blad kvar och alla interna noder måste således under resans gång ha omvandlats till blad, det vill säga fått sin grad reducerad till ett. Men detta innebär ju att kanter som ledde från de interna noderna till blad försvunnit och att noden således blivit antecknad i sekvensen åtminstone en gång.

Kalla trädets ordning för n, dess noder för N(1),... N(n), Prüfersekvensen för P, och elementen i sekvensen för P(1), ... P(n-2). Vi konstaterade nyss att vi har kunskap om vilka noder som är blad och vilka som är interna i det fulla, "ursprungliga" trädet - vi för upp alla bladen på en lista L. Vi vet också att det första vi gjorde när vi skapade sekvensen var att plocka bort det lägsta bladet på trädet (det vill säga det lägsta elementet i L) och att Prüfersekvensens första element anger från vilken nod (P(1)) detta blad plockades bort - så vi förbinder det lägsta bladet och P(1) med en kant. Vi stryker det "bortplockade" (eller kanske "tillagda"?) bladet från L och, om P(1) ej förekommer fler gånger i P så vet vi att P(1) blev ett blad genom operationen. Om P(1) blev ett blad tillfogar vi P(1) till L.

Vi har nu återskapat läget inför bortplockandet av det andra bladet från trädet! Vår nya L innehåller alla blad i det "nya" trädet av ordning n-1 när vi plockat bort det första bladet (genom att vi strök "L(1)" och eventuellt tillförde P(1)) och P(2),... P(n) anger från vilka noder bladen plockats från detta. Så, förbind det lägsta bladet i L och P(2) med en kant, stryk bladet från L och, om P(2) blev ett blad så tillfogar vi P(2) till L. Genom att fortfara på samma sätt till och med P(n-2), det vill säga genom hela sekvensen, återskapas trädet steg för steg.

När vi är klara med hela sekvensen får vi en nod kvar som inte är förbunden med de andra (noden som står sist i den lexikografiska ordningen, N(n), denna kan ju inte någonsin vara minst). N(n) var den ena av de två återstående noderna efter att trädet skapats, men den andra var den nod som det sista bladet plockades från och som står sist i sekvensen, P(n-2). Som sista åtgärd förenar vi därför N(n) och P(n-2) med en kant och trädet är helt återskapat.

Vi ser nu att varje Prüfersekvens som erhållits från ett orotat märkt träd återskapar detsamma.

Exempel: I exempel 1 under hur man skapade sekvenser från träd fick vi sekvensen {4,4,4,5} från det givna trädet. Bilderna ovan illustrerar hur detta träd återskapas steg för steg. Vi ser att, eftersom sekvensens längd är fyra, så är trädets ordning sex - det finns alltså sex noder {1,2,3,4,5,6}, varav två är interna {4,5} och resten blad {1,2,3,6}. Vi för upp bladen på L={1,2,3,6}.

Steg 1:Det lägsta bladet är nod 1 så vi förbinder detta med den första noden i vår sekvens, P(1), och resultatet av detta framgår av den första bilden. Vi stryker nod 1 från L och eftersom noden 4 förekommer fler gånger i P så blev den inget blad denna gång - inför "steg 2" är alltså L={2,3,6}.

Steg 2: Vi förbinder det lägsta bladet (nod 2) i L med P(2)=4, stryker nod 2 från L och konstaterar att noden 4 fortfarande är intern så den blev inget blad den här gången heller. Inför "steg 3" har vi alltså L={3,6}

Steg 3: Det lägsta bladet i L är nod 3 så detta förbinder vi med P(3)=4. Vi stryker nod 3 från L och nu förekommer inte nod 4 fler gånger i P (den blev alltså ett blad i detta steg när sekvensen skapades) så nu lägger vi till nod 4 till L, sålunda inför "steg 4": L={4,6}

Steg 4: Nod 4 är nu det lägsta bladet i L varför vi förbinder den med P(4). Nod 5 blev härigenom också ett blad, de interna noderna är slut och L={5,6} Det återstår alltså bara "steg 5":

Steg 5: Vi förbinder den sista noden i sekvensen P(4), d.v.s. nod 5, med den högsta noden (nod 6), vilket ju är detsamma som att förbinda de två kvarvarande bladen i L. Trädet är klart!

Hur man återskapar ett rotat märkt träd från dess Prüfersekvens

Liksom vid skapandet av sekvensen, skiljer sig inte förfaringssättet mycket från det orotade fallet. Trädets kanter är återskapade efter n-2 steg precis som ovan för ett orotat träd och det extra steget avgör bara vilken av noderna som är rot, vilket anges av det sista elementet i sekvensen.

Bijektivitet och Cayleys formel för orotade märkta träd

Ovan har vi konstaterat att varje rotat märkt träd ger en unik Prüfersekvens, och att varje Prüfersekvens som skapats från ett orotat märkt träd ger upphov till det träd sekvensen skapats från. Vi har alltså en bijektion från träden till de sekvenser som de genererar.

Vid återskapandet av ett orotat märkt träd från dess Prüfersekvens konstaterade vi att alla noder som inte finns i sekvensen är blad i det fullständiga ("ursprungliga") träd som sekvensen skapades från. Eftersom sekvensen innehåller n-2 noder (av totalt n) finns det alltså minst två blad i det ursprungliga trädet (finns det bara två blad är trädet en enda kedja med ett blad i varje ände). Dessa "ursprungliga" blad förde vi upp på listan L, från vilken vi väljer noder att sammankoppla med de noder som anges i sekvensen. Varje gång vi väljer en nod från L tar vi bort den från listan, men eftersom det samtidigt återstår en nod mindre i sekvensen att bearbeta (sekvensens "längd" minskar på så sätt också med ett) så finns det hela tiden minst två noder i L (antalet går inte under två eftersom vi av och till "för över noder från sekvensen till L").

När vi börjar återskapandet har vi n noder som har graden noll, som vi kan betrakta som n tomma delträd i en skog. Varje gång vi sammankopplar en nod i L med en nod i sekvensen skapar vi en kant mellan två noder så att två delträd förenas, och det totala antalet delträd i skogen minskar med ett. När sekvensen är slut har vi skapat n-2 kanter mellan delträden och sålunda återstår två delträd. Det avslutande steget är att sammankoppla de två "kvarvarande" noderna i listan L så att dessa två delträd förenas till ett träd. Men detta innebär ju att oavsett vilka noder vi än har i sekvensen och i vilken ordning de än står så får vi ett träd som resultat. Sålunda har vi också att, eftersom varje sekvens ger upphov till det träd den skapats från, att antalet orotade märkta träd med n noder är lika med antalet möjliga Prüfersekvenser av längden n-2. Eftersom detta antal är lika med n^n-2, så är också antalet orotade märkta träd med n noder lika med detta antal, varför Cayleys formel för orotade märkta träd är bevisad:

$T_{n}=n^{n-2}$

Bijektivitet och Cayleys formel för rotade märkta träd

Skillnaden mellan ett rotat och orotat träd är bara den att i ett rotat träd finns det en nod som har tilldelats "egenskapen att vara rot", så i varje orotat märkt träd med n noder finns det alltså n olika noder att välja som rot. Det finns därför såklart nT_n = n^n-1 rotade märkta träd med n noder vilket ju är Cayleys formel för rotade märkta träd:

$T_{n}=n^{n-1}$

Eftersom Prüfersekvensen för ett rotat träd innehåller informationen som ett extra element, och de n-2 föregående elementen i sekvensen skapar det märkta trädet, följer det även ur detta (om än ej lika solklart).

Övriga tillämpningar

• Cayleys formel kan stärkas genom att visa nedanstående påstående:

Antalet uppspännande träd i en komplett graf $K_{n}$ med graderna $d_{1},d_{2},\ldots ,d_{n}$ är lika med multinomialkoefficienten

${\binom {n-2}{d_{1}-1,\,d_{2}-1,\,\dots ,\,d_{n}-1}}={\frac {(n-2)!}{(d_{1}-1)!(d_{2}-1)!\cdots (d_{n}-1)!}}.$

Beviset följer ur observationen, som vi gjorde ovan när vi skapat sekvensen för ett märkt orotat träd, att antalet gånger en nod förekommer i Prüfersekvensen är lika med dess grad minus ett: d.v.s. noden i förekommer d_i - 1 gånger.

• Att slumpvis generera jämnt fördelade Prüfersekvenser och omvandla dem till motsvarande träd är ett enkelt sätt att slumpartat generera jämnt fördelade märkta träd.

Externa länkar

• Prüfer Sequence på ProofWiki.