Grafteori

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.

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 ${\displaystyle \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.

• En vandring (walk på engelska) är en följd av noder i grafen där den föregående noden har en båge till nästa.^[1]
• En väg (trail på engelska) är en vandring som inte passerar samma båge flera gånger.^[1]
• En stig (path på engelska) är en vandring som inte passerar samma nod flera gånger.^[1]
• En krets (circuit på engelska) är en sluten väg, det vill säga börjar och slutar i samma nod.^[1]
• En cykel (cycle på engelska) är en sluten stig, det vill säga börjar och slutar i samma nod.^[2]
• En eulerväg är en väg som passerar varje båge en gång.^[3]
• En eulerkrets är en krets som passerar varje båge en gång.^[3]
• En hamiltonstig är en stig som passerar varje nod en gång.^[3]
• En hamiltoncykel är en cykel som passerar varje nod en gång.^[3]
• Hörn som är förbundna med varandra med en eller flera kanter kallas grannar. Mängden av grannar till ett hörn ${\displaystyle u}$ betecknas ofta ${\displaystyle N(u)}$. Antalet bågar från hörnet kallas hörnets grad (degree på engelska).^[2]
• En graf G=(V, E) kallas sammanhängande om det finns en stig mellan varje par av noder i grafen. Då har den endast har en komponent. De som inte är sammanhängande har flera komponenter.^[2]
• En komplett graf, ofta betecknad ${\displaystyle K_{n}}$, är en graf där det finns en kant mellan varje par av hörn och där antalet hörn är ${\displaystyle n}$ stycken.^[4]
• En bipartit graf (bipartite graph på engelska) har två delmängder av noder så att alla bågar går från den ena mängden till den andra.^[4]
• En komplett bipartit graf (complete bipartite graph på engelska) har bågar från varje nod i den ena mängden till varje nod i den andra. Beteckningen är ${\displaystyle K_{n_{1},n_{2}}}$ där ${\displaystyle n_{1}}$ och ${\displaystyle n_{2}}$ är antalet element i respektive mängd.^[4]
• En multigraf G = (V,E) består av en mängd ${\displaystyle V}$ av noder, en mängd ${\displaystyle E}$ av kanter och en funktion ${\displaystyle f:E\rightarrow {{u,v}|u,v\in V\wedge u\neq v}}$. Kanterna ${\displaystyle e_{1}\in E}$ och ${\displaystyle e_{2}\in E}$ kallas multipla eller parallella om ${\displaystyle f(e_{1})=f(e_{2})}$.^[3]
• En pseudograf G=(V,E) består av en icke tom mängd av V noder, en mängd E kanter och en funktion ${\displaystyle f:E\rightarrow {{u,v}|u,v\in V}}$. En kant ${\displaystyle e}$ där ${\displaystyle f(e)={v,v}}$ är en ögla (loop på engelska). Med andra ord så är en pseudograf en multigraf med multipla kanter och loopar.
• 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. Alltså tillåts varken parallela kanter eller öglor.^[5]

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 finns det en eulerskrets, 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 och får en eulerväg^[3]

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.

Till en planär graf ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle G}$ konstrueras en kant i ${\displaystyle G^{*}}$ som förbinder de två punkter i ${\displaystyle G^{*}}$ som är ritade i de två ytor som avgränsas av kanten i ${\displaystyle G}$, där den konstruerade kanten bara får korsa en kant i ${\displaystyle G}$. Då är också ${\displaystyle G^{*}}$ en planär graf ritad i samma plan som ${\displaystyle G}$ och den har lika många kanter som ${\displaystyle G}$, lika många ytor som ${\displaystyle G}$ har punkter och vice versa. Som kurvor ritade på en sfär är ${\displaystyle G}$ och ${\displaystyle 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.

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.

Leonhard Eulers uppsats om Königsbergs sju broar år 1736 anses vara det första resultatet inom grafteorin.^[6]

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.

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

• Dijkstras algoritm
• Kruskals algoritm
• Prims algoritm

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.

• Alon, Noga
• Berge, Claude
• Bollobás, Béla
• Bondy, Adrian John
• Brightwell, Graham
• Chudnovsky, Maria
• Chung, Fan
• Dirac, Gabriel Andrew
• Erdős, Paul
• Euler, Leonhard
• Faudree, Ralph
• Golumbic, Martin
• Graham, Ronald
• Harary, Frank
• Heawood, Percy John
• Kotzig, Anton
• Kőnig, Dénes
• Lovász, László
• Murty, U. S. R.
• Nešetřil, Jaroslav
• Rényi, Alfréd
• Ringel, Gerhard
• Robertson, Neil
• Seymour, Paul
• Szemerédi, Endre
• Thomas, Robin
• Thomassen, Carsten
• Turán, Pál
• Tutte, W. T.
• Whitney, Hassler

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

• Grannmatris
• https://web.archive.org/web/20131111192705/https://www.doria.fi/bitstream/handle/10024/2841/kolmival.pdf?sequence=1

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

• Eriksson, Kimmo; Hillevi Gavel (2002). Diskret matematik och diskreta modeller. Lund: Studentlitteratur. ISBN 91-44-02465-7