Träd (graf)

Från Rilpedia

Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif
icon_anmal.gif
rp-wp-sv.gif
Skog med tre träd

I grafteori är ett träd en enkel sammanhängande graf utan cykler och om grafen skulle bestå av fler komponenter, som även de är träd, så kallas det en skog.

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.

Innehåll

Historik

Träd dök för första gången upp underförstått i Gustav Kirchhoff verk, som använde grafteoretiska ideér i sina uträkningar av elektriska kretsar. Några år senare var der Arthur Cayley som gjorde 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 nn−2 för 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 CH4 (metan) och C2H5OH (etanol) var kända, men man hade inte förståt hur atomerna var sammanbundna för att skapa dessa molekyler. Kring den här tiden började ideé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 molekylegrupper. Tabellen nedan visar antalet av de 8 första alkanierna.


Beteckning CH4 C2H6 C3H8 C4H10 C5H12 C6H14 C7H16 C8H18
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 (t.ex. 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 alltid den billigaste kanten. 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 isomorpi 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 entydigt bestämd en 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, skapars exakt en cykel.
  • Grafen G är sammanhängade 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örbunda med en kant inte har samma "färg".

Det kromatiska polynom, på ett träd med n noder, säger på hur många sett man kan "färga" en graf med λ olika "färger" och är λ(λ − 1)n − 1. (Här ser man att minsta naturliga tal som fungerar är det kromatiska talet, dvs λ = 2).

Räknande av träd

Började som sagt var med Cayley på 1800-talet och gick ett stort steg framåt med ett arbete av Pólya 1937, där kombinerades de klassiska ideérna 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, nn-2
  • Antal märkta rotade träd med n noder ges, nn-1
  • Antal rotade träd med n noder ges genom att använda den genererande funktionen r(x)=\sum_{n=1}^{\infty} R_nx^n=x+x^2+2x^3+4x^4+20x^6+ \cdots där Rn ä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} dvs ingen explicit formel att använda direkt.

Bevis

Den kompletta listan av träd med 2,3,4 märkta noder: 22 − 2 = 1 träd med 2 noder, 33 − 2 = 3 träd med 3 noder och 44 − 2 = 16 träd med 4 noder.

Detta är ett bevis på Cayleys formel av Prüfer och 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). Bortagandet 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 T1 ,...,Tk 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 vwi där wi ligger i Ti, 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. Eftersom B kan väljas på T(n, k) sätt och antalet sätt att sammanfoga wi till noder i någon annan Tj är (n−i)−ni (där ni betecknar antalet noder i Tj) det följer att det totala antalet länkar (A, B) är T(n, k)((n−1−n1)+...+(n−1+nk)=(n−1)(k−1)T(n, k) ty (n1+...+nk) = (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}

Sedan av summeringen ö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}

Referenser

  • Wilson, Robin J.: Introduktion to Graph Theory, Longman, New York 1985, 3:e (engelska). 0-582-44685-6. 
  • Gross, Jonathan L. and Yellen, Jay: Handbook of Graph Theory, CRC Press, 2004, Discrete Mathematics and its Applications (Boca Raton) (engelska). 1-58488-090-2. 
  • Astratian, Armen; Björn, Anders och Turesson, Bengt Ove: Diskret Matematik, Matematiska institutet, Linköping 2007. 
Hämtad från "https://sv.rilpedia.org/wiki/Tr%C3%A4d_(graf)"
Personliga verktyg