Grafteori

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. En väg i en graf är en sekvens av noder sådan att det från varje nod (förutom möjligen den sista) i sekvensen finns en båge till nästa nod i sekvensen.

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 boolesk funktion $\psi (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 reella 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 visualisering 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 beskrev Leonhard Euler 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 eller Eulercykel ä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.

Duala grafen

Till en planär graf $G$ som är ritad (inbäddad) i ett plan utan att kanter korsar varandra (en så kallad plan graf) kan man konstruera den duala grafen $G^{*}$ på följande sätt: välj en punkt i varje yta i grafen, inklusive ytan utanför grafen; för varje kant i $G$ konstrueras en kant i $G^{*}$ som förbinder de två punkter i $G^{*}$ som är ritade i de två ytor som avgränsas av kanten i $G$ , där den konstruerade kanten bara får korsa en kant i $G$ . Då är också $G^{*}$ en planär graf ritad i samma plan som $G$ och den har lika många kanter som $G$ , lika många ytor som $G$ har punkter och vice versa. Som kurvor ritade på en sfär är $G$ och $G^{**}$ homeomorfa, vilket betyder att de kan deformeras kontinuerligt till varandra på sfären.

Duala grafer är speciellt användbara därför att många egenskaper är likartade för en planär graf och dess duala graf, vilket ibland kan användas i bevis för egenskaper hos grafen.

Den duala grafen för en uppritad plan graf är unik (två olika duala grafer är isomorfa), men olika sätt att rita grafen kan ge icke-isomorfa duala grafer.

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

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_{0},e_{0},v_{1},e_{1},...,e_{k-1},v_{k}$ , v är hörn och e kanter, kallas för en väg av längd k.
Om en väg har samma startnod $v_{0}$ 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 hörn och av E en mängd av oordnade par av hörn som kallas kanter.
En komplett graf, ofta betecknad $K_{n}$ , är en graf där det finns en kant mellan varje par av hörn och där antalet hörn är n stycken.
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.
En graf G=(V, E) kallas sammanhängande om den endast har en komponent.

Kända grafteoretiker

Se även

Den här artikeln ingår i boken:
Grafteori

Referenser

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