Träd (graf)

I grafteori är ett träd en enkel sammanhängande graf utan cykler. En graf som består av flera komponenter, som alla var för sig är träd, kallas en skog.

Historik

Träd dök för första gången upp underförstått i Gustav Kirchhoffs verk, som använde grafteoretiska idéer i sina uträkningar av elektriska kretsar. Några år senare gjorde Arthur Cayley framsteg genom att räkna rotade träd, senare lyckades även han hitta en metod som löste problemet med att räkna träd utan rötter. 1889 presenterade Cayley formeln nⁿ⁻² för att beräkna antal märkta träd med n:st noder, det var dock Heinz Prüfer som gav ett korrekt bevis.

Redan på 1850 kände man till att kemikalier var kombinerade i bestämda mängder. Kemiska formler såsom CH₄ (metan) och C₂H₅OH (etanol) var kända, men man hade inte förstått hur atomerna var sammanbundna för att skapa dessa molekyler. Kring den här tiden började idén om valenselektroner accepteras, särskilt när Alexander Crum Brown presenterade sin grafmodell för att representera molekyler. Crum Browns grafmodell förklarade för första gången fenomenet med isomeri. Cayley använde metoder för räkning av träd för att bestämma antalet alkaner upp till 11 kolatomer, men han beräknade även antalet av flera andra molekylgrupper. Tabellen nedan visar antalet av de 8 första alkanerna.

Beteckning	CH₄	C₂H₆	C₃H₈	C₄H₁₀	C₅H₁₂	C₆H₁₄	C₇H₁₆	C₈H₁₈
Antal	1	1	1	2	3	5	9	18

Definitioner

Ett uppspännande träd är en delgraf i en sammanhängande graf G så att varje nod i G finns i trädet. En intressant användning här är om man ger alla kanterna i en enkel graf ett värde (till exempel kostnad för elnät). Detta kallas en viktad graf. I många fall vill man hitta det billigaste alternativet och detta kan man få ut av Kruskals algoritm som går ut på att man alltid använder den billigaste kanten förutsatt att ingen cykel bildas. Den delgraf som produceras av algoritmen är ett uppspännande träd.

Ett märkt träd är ett träd där varje nod har en unik markering så som 1,2,3,...,n. Två märkta träd anses lika om det finns en isomorfi från den ena till den andra så att märkningen bevaras.

Ett riktat träd är en riktad graf som skulle varit ett träd om den inte var riktad och med en riktad graf menas att kanten bara går åt ett håll, som en enkel riktad väg.

Ett rotat träd är träd där man valt ut en nod i trädet, och kallar den för en rot, som utgör basen för trädet. Två rotade träd anser lika endast om det finns en isomorfi från den ena till den andra som avbildar roten från den första till roten av den andra. Rotade träd används på många ställen, bland annat inom sannolikhetslära i matematiken.

Egenskaper

Om vi låter grafen G vara en enkel graf så är dessa fem villkor ekvivalenta

Grafen G är ett träd
För varje par noder u, v så finns det en entydigt bestämd väg mellan u och v
Grafen G är sammanhängande och tar man bort vilken som helst av kanterna i G, får man en osammanhängande graf
Grafen G saknar cykler och lägger man till en kant mellan två noder i G, som inte redan är förbundna, skapas exakt en cykel.
Grafen G är sammanhängande och $|V(G)|=|E(G)|+1$

Lemma: Träd med mer än två noder har minst två löv, noder med gradtalet ett.

Ett träds kromatiska tal är två, det kromatiska talet säger hur många "färger" som behövs för att "färga" grafen så att två noder som är förbundna med en kant inte har samma "färg".

Det kromatiska polynomet, på ett träd med n noder, säger på hur många sätt man kan "färga" en graf med λ olika "färger" och är $\lambda (\lambda -1)^{n-1}$ . (Här ser man att minsta naturliga tal som fungerar är det kromatiska talet, det vill säga λ = 2).

Räknande av träd

Räknande av träd inleddes med Cayley på 1800-talet och gick ett stort steg framåt med ett arbete av Pólya 1937, där kombinerades de klassiska idéerna med genererande funktioner och de med permutationer. Senare resultat i räknande av träd kom genom R. Otter och andra.

Några exempel på hur man räknar ut antal träd

Antal märkta träd med n noder ges av Cayleys formel, n^n-2
Antal märkta rotade träd med n noder ges, n^n-1
Antal rotade träd med n noder ges genom att använda den genererande funktionen $r(x)=\sum _{n=1}^{\infty }R_{n}x^{n}=x+x^{2}+2x^{3}+4x^{4}+20x^{6}+\cdots$ där R_n är antalet träd med n noder. För att få ut den behöver man även den återkommande relationen $r(x)=x\prod _{i=1}^{\infty }(1-x^{i})^{-R_{i}}$ det vill säga ingen explicit formel att använda direkt.

Bevis

Detta är ett bevis av Cayleys formel av L. E. Clarke.

Låt T(n, k) beteckna antalet märkta träd med n noder i vilken en given nod, v, har gradtalet k. Vi ska härleda ett uttryck för T(n, k) och uttrycket skall sedan summeras från k = 1 till k = n−1.

Låt A vara godtyckligt märkt träd i vilken d(v) = k−1 (d(v) gradtal av v). Borttagandet av en kant som ej hör till v, kallar den wz, lämnar två delträd, ena innehållande v och antingen w eller z (vi väljer w) och den andra innehåller z. Om vi nu sammanfogar träden med en kant mellan v och z, så får vi ett märkt träd där d(v) = k. Vi ska kalla ett par (A, B) av märkta träd en länk om B kan fås från A genom ovanstående konstruktion. Vårt mål är att räkna det totala antalet länkar. Då A kan väljas på T(n, k) sätt och B är unikt definierad av kanten wz som kan väljas på (n−1)−(k−1)=(n−k) sätt. Detta leder till att det totala antalet länkar (A, B) är (n−k)T(n, k−1). Å andra sidan, låt B vara ett märkt träd i vilken d(v) = k och låt T₁ ,...,T_k vara delträd till B som erhålls då noden v tas bort och varje tillhörande kant till v. Då kan vi få ett märkt träd A i vilket d(v) = k-1 genom att ta bort precis en kant, säg vw_i där w_i ligger i T_i, från B. Det är klart att det motsvarande paret (A, B) av märkta träd är en länk och att alla länkar kan fås på detta sätt.^{[förtydliga]} Eftersom B kan väljas på T(n, k) sätt och antalet sätt att sammanfoga w_i till noder i någon annan T_j är (n−i)−n_i (där n_i betecknar antalet noder i T_j) det följer att det totala antalet länkar (A, B) är T(n, k)(n−1−n₁)+...+(n−1+n_k)=(n−1)(k−1)T(n, k) ty (n₁+...+n_k) = (n−1)

Vi har visat att (n−k)T(n, k−1) = (n−1)(k−1)T(n, k). Med upprepning och användning av uppenbar fakta att T(n, n−1) = 1 ser vi att

T(n,k)={{n-2} \choose {k-1}}(n-1)^{n-k-1}

Genom summering över alla möjliga värden på k följer att antalet T(n) av märkta träd med n noder ges av

$T(n)=\sum _{k=1}^{n-1}{{n-2} \choose {k-1}}(n-1)^{n-k-1}=((n-1)+1)^{n-2}=n^{n-2}$

Tillämpningar

Den biologiska systematiken är ett exempel på omfattande användning av träd. Även inom lingvistik är det vanligt att träd används, nämligen för att representera syntaktisk struktur. Se frasstrukturgrammatik och dependensgrammatik.

Referenser

Wilson, Robin J. (1985) (på engelska). Introduction to Graph Theory (3:e). New York: Longman. 0-582-44685-6

Gross, Jonathan L. and Yellen, Jay, red (2004) (på engelska). Handbook of Graph Theory. Discrete Mathematics and its Applications (Boca Raton). CRC Press. 1-58488-090-2

Astratian, Armen; Björn, Anders och Turesson, Bengt Ove (2007). Diskret Matematik. Linköping: Matematiska institutet