Grafteori

Från Rilpedia

Texten från svenska Wikipedia

En graf med sex noder och sju bågar. Grafen är planär och sammanhängande, däremot inte komplett. Den saknar också Eulervägar eftersom den har mer än två noder med udda antal bågar, vilket kräver att man någon gång går längs samma båge två gånger för att kunna gå längs alla bågar.

Grafteori är det område inom matematiken som undersöker egenskaper hos grafer. En graf är en mängd punkter, kallade noder eller hörn, sammanbundna med linjer, kallade bågar eller kanter. Anledningen till att man valt orden noder och bågar eller kanter och hörn istället för punkter och linjer är att kanter och hörn saknar de vanliga euklidiska egenskaperna för punkter och linjer. Man kan lägga flera punkter på samma linje, men en kant kan bara gå mellan max två hörn. Kanten kan dessutom gå tillbaka till samma hörn. Den kallas då loop. Antalet kantändar som ansluter till samma hörn kallas hörnets grad. Det är möjligt att flera kanter går mellan samma par av hörn. Det kallas multipla kanter.

Historia

Leonhard Eulers uppsats om Königsbergs sju broar år 1732 anses vara det första resultatet inom grafteorin.

Definition

En graf G(V(G),E(G)) består av två mängder V(G), kallad nodmängden, eller hörnmängden, och E(G), kallad bågmängden, eller kantmängden, där V(G) är en godtycklig mängd och E(G) är en mängd bestående av oordnade eller ordnade par av element ur V(G). Är paren ordnade kallas grafen riktad alternativt en digraf, annars kallas den oriktad.

Den ovanstående definitionen gäller för grafer i allmänhet. Det är dock vanligt att endast betrakta så kallade enkla grafer. Då tillåts inte några par av typen {x,x} i E(G) och E(G) får då inte heller vara en multimängd.

Alternativa definitioner förekommer, till exempel definieras en graf ibland som en mängd av noder, en mängd av kanter samt en booelsk funktion ψ(v,e) som ordnar talet ett om och endast om v är en ändpunkt av e och noll annars.

Beroende på tillämpningen kan kanterna även ges olika vikter, dvs positiva rella tal. Om kanterna har vikter kallas grafen för viktad graf.

Observera även att en graf inte tillskrivs några Euklidiska egenskaper med undantag för föregående anmärkning. Grafen är definierad av de två beskrivna mängderna och alltså inte av den visulisering man med lätthet skapar utifrån definitionen. En sådan visualisering kallas en inbäddning av grafen.

Normalt tar man inom grafteorin inte någon hänsyn till hörnens storlek. På samma sätt kan kanterna betraktas som gummiband, det är tillåtet att forma om grafen genom att ändra deras längd och även hur de böjer sig, den saknar betydelse i de flesta fall. Däremot brukar man inte tillåta att omforma grafen på ett sätt som kräver att man att bryter upp kanterna.

Eulervägar

I en skrivelse 1732 Leonhard Euler beskrev begreppet som numera kallas Eulerväg och skapade därmed grafteorin.

En Eulerväg är en väg som går längs varje kant i grafen exakt en gång. Däremot är det tillåtet att passera samma hörn flera gånger om det har flera kanter. En Eulerkrets är en Eulerväg som börjar och slutar i samma hörn.

Om "Eulers väg" ska gå att genomföra så handlar det om hur många udda hörn som finns i "figuren". För att veta om ett hörn är udda eller inte räknar man hur många linjer som strålar ut från detta hörn, om talet är udda är hörnet udda.

Om det inte finns några udda hörn i "figuren", gäller Eulers väg, genom att man börjar och slutar i samma hörn/på samma punkt. Den gäller också ifall det finns två udda hörn, här börjar man på det ena udda hörnet och avslutar på det andra udda hörnet.

Planära grafer

Kanter som korsar varandra har ingen förbindelse med varandra, det är bara i hörnen man kan gå från en kant till en annan. En graf kallas planär om det är möjligt att rita den i ett plan, till exempel på ena sidan av ett papper, utan att några kanter korsar varandra. Alla grafer med högst fyra hörn är alltid planära grafer. Har grafen fler än fyra hörn beror det på kanternas sträckning om den är planär. Observera att egenskapen gäller frågan om det är möjligt att rita grafen så, inte hur den faktiskt är ritad.

Planära grafer och teorin bakom dem är ett viktigt exempel på tillämpningar av grafteorin.

Färgningar

En färgning av en graf innebär att man tilldelar elementen i nodmängden färger. En korrekt färgning är då en färgning där ingen kant har ändpunkter tilldelade samma färg. Teorin om färgningar har många tillämpningar. Mer specifikt anger det kromatiska polynomet, betecknat P(G,λ), antalet sätt man kan färga en graf korrekt då man har tillgång till λ distinkta färger. Det minsta naturliga tal χ(G), för vilket P(G,λ)=0, kallas det kromatiska talet för G. Fyrfärgssatsen kan formaliseras som att χ(G)<5 för alla planära grafer G. Det finns många tillämpningar av färgningar, bland annat på latinska kvadrater.

Algebraisk grafteori

Inom den algebraiska grafteorin använder man algebraiska metoder för att beskriva egenskaper hos grafer. Norman Biggs är en av pionjärerna inom området.

Algoritmisk grafteori

Inom den algoritmiska grafteorin studerar man algoritmer för att avgöra olika egenskaper hos grafer.

Viktiga algoritmer

• Dijkstras algoritm
• Kruskals algoritm
• Prims algoritm

Probabilistisk grafteori

Inom den probabilistiska grafteorin studerar man slumpgrafer och dess egenskaper. Området grundlades av Paul Erdös under 1940- och 1950-talet med ett antal publikationer där han med sannolikhetsteoretiska metoder visade på existenser av grafer med vissa egenskaper utan att faktiskt konstruera dem. Bland annat gav Erdös en exponentiell undre gräns för vissa Ramseytal samt visade att det givet naturliga tal k och g så finns det k-kromatiska grafer med en midja av storlek g eller större.

Olika grafteoretiska objekt

En cykel eller krets är en väg som återgår till starthörnet. Den kan gå antingen via en loop eller via andra hörn.

• Hörn som är förbundna med varandra med en eller flera kanter kallas grannar. Mängden av grannar till ett hörn u betecknas ofta N(u).
• En följd av noder och bågar ur G, P = v₀,e₀,v₁,e₁,...,e_k,v_k kallas för en väg av längd k..
• Om en väg har samma startnod v₀ som slutnod v_k och består av i övrigt distinkta noder och bågar, kallas den för en cykel.
• En enkel graf G=(V,E) består av V; en icke tom mängd av noder och av E en mängd av oordnade par av element som kallas kanter.
• En komplett graf, ofta betecknad K_n, är en graf där det finns en kant mellan varje par av element ur V(G), och där |V(G)|=n, dvs om alla hörn i grafen har minst en kant förbunden med varje annat hörn i grafen kallas den en komplett graf.
• En multigraf G=(V,E) består av en mängd av V noder, en mängd E kanter och en funktion f:E →{{u,v} | u,v ∈ V och u ≠ v}. Kanterna e₁∈Ε och e₂∈E kallas multipla eller parallella om f(e₁) = f(e₂)
• En pseudograf G=(V,E) består av en icke tom mängd av V noder, en mängd E kanter och en funktion f:E →{{u,v} | u,v ∈ V}. En kant e där f(e) ={v,v} med andra ord så är en pseudograf en multigraf med multipla kanter och loopar.

Referenser

A.Asratian, A.Björn, B.O. Turesson: Diskret matematik. Linköping 2006