Grafteori

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. Observera att en loop har två kantändar i samma hörn. Det är möjligt att flera kanter går mellan samma två hörn. Det kallas multipla kanter.

Beroende på tillämpningen kan kanterna även ha en riktning samt ges olika vikter. Om kanterna har riktning kallas grafen för 'riktad graf eller digraf.

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.

En väg (path) är en förflyttning genom grafen som börjar i ett hörn och följer kanterna till ett eller flera andra hörn.

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.

En graf kallas sammanhängande om det är möjligt att finna en väg via kanter och hörn från vilket hörn som helst till samtliga andra hörn i grafen.

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 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.

Hörn som är förbundna med varandra med en eller flera kanter kallas grannar (neighbours).

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 ett papper, utan att några kanter korsar varandra. Alla grafer med högst fyra hörn är alltid planära grafer. Han grafen fler än fyra hörn beror det på kanternas sträckning om den är planar. Observera att egenskapen gäller frågan om det är möjligt att rita grafen så, inte hur den faktiskt är ritad.

[redigera] Historia

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

[redigera] 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.

[redigera] Algoritmisk grafteori

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

[redigera] Viktiga algoritmer

• Dijkstras algoritm
• Kruskals algoritm
• Prims algoritm

[redigera] Stokastisk grafteori

Inom den stokastiska 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 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.

[redigera] Olika typer av grafer

• En enkelgraf 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 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.