Grafteori

Punkter och linjer mellan dem: mer än så är inte en graf. Ändå beskriver samma bild en vägkarta, ett nätverk av vänner, en molekyl och internet, och frågorna man kan ställa om den, från hur många färger den behöver till om den kan ritas i ett streck, har hållit matematiker sysselsatta sedan 1736.

En graf med tio hörn, Petersengrafen, med hörnen färgade i tre färger så att ingen kant förbinder två hörn med samma färg
En graf med tio hörn, Petersengrafen, med hörnen färgade i tre färger så att ingen kant förbinder två hörn med samma färg

Hörn och kanter

En graf har hörn, även kallade noder, och kanter som var och en förbinder två hörn. Var hörnen ritas spelar ingen roll, bara vilka par som är förbundna, så samma graf kan se mycket olika ut på papperet. Graferna på lekplatsen är enkla: ingen kant från ett hörn till sig självt och högst en kant mellan två hörn. Med n hörn kan det finnas högst n(n − 1) / 2 kanter; en graf som har alla kallas komplett, och K5 är den kompletta grafen på fem hörn.

Grader och handskakningslemmat

Ett hörns grad är antalet kanter som möts i det. Lägg ihop alla grader så får du exakt dubbla antalet kanter, eftersom varje kant har två ändar och räknas en gång i varje. Det är handskakningslemmat: i varje grupp blir handskakningarna, räknade person för person, tillsammans dubbelt så många som antalet handskakningar. Det betyder också att antalet hörn med udda grad alltid är jämnt. En graf där varje hörn har samma grad k kallas k-reguljär.

Sammanhängande grafer, träd och cykler

En graf är sammanhängande när man kan ta sig från varje hörn till alla andra längs kanterna; annars faller den isär i delar, så kallade komponenter. En cykel är en rundtur som kommer tillbaka till starten utan att använda något hörn två gånger, och längden av den kortaste cykeln är grafens midja. En sammanhängande graf utan cykler är ett träd, och ett träd med n hörn har alltid exakt n − 1 kanter: en färre och det faller isär, en till och det får en cykel. Varje sammanhängande graf innehåller ett uppspännande träd, ett träd som når alla hörn med bara några av kanterna.

Bipartita grafer och färgning

Färga hörnen så att ingen kant förbinder två hörn med samma färg. Det minsta antal färger som klarar det är det kromatiska talet. En färg räcker bara om det inte finns några kanter. Två färger räcker precis när grafen är bipartit: hörnen delas upp i två sidor och varje kant går tvärs över. Dénes Kőnig visade 1936 att det är samma sak som att sakna cykler av udda längd, eftersom en udda cykel inte kan växla mellan två färger hela vägen runt. För tre eller fler färger känner man inte till något lika enkelt test: att avgöra om tre färger räcker är NP-fullständigt, så program får söka, precis som lekplatsen gör.

Ett exempel: Petersengrafen

Ta en femhörning A–B–C–D–E och en femuddig stjärna F–H–J–G–I inuti den, och förbind varje hörn i femhörningen med en udd på stjärnan: A–F, B–G, C–H, D–I och E–J. Det är Petersengrafen, med 10 hörn och 15 kanter. Varje hörn har grad 3, så graderna blir tillsammans 30, dubbelt så mycket som 15. Dess kortaste cykel har längden 5, så den saknar trianglar, men femhörningen är en udda cykel, så den är inte bipartit och behöver 3 färger. Två godtyckliga hörn ligger högst 2 kanter ifrån varandra, så dess diameter är 2. Alla tio grader är udda, så den saknar Eulerväg, och den kan inte ritas utan korsningar.

Eulervägar och Königsbergs broar

Staden Königsberg hade sju broar som förband fyra landområden, och folk undrade om man kunde gå över varje bro exakt en gång. År 1736 visade Leonhard Euler att det inte gick, och grafteorin var född. Varje gång en promenad passerar ett landområde använder den två broar, så bara start och mål får ha ett udda antal broar, och alla fyra landområdena i Königsberg hade ett udda antal. En väg som använder varje kant en gång kallas i dag en Eulerväg, eller en Eulerkrets när den slutar där den började. Carl Hierholzer bevisade 1873 att villkoret också räcker: om alla kanter hänger ihop i ett stycke och högst två grader är udda finns vägen, och hans metod att foga ihop rundturer används fortfarande för att hitta den.

En historisk fågelperspektivkarta över Königsberg (Koningsberga), som visar Pregel och ön i hjärtat av de sju broarnas problem. År 1736 visade Leonhard Euler att ingen promenad kunde korsa varje bro exakt en gång, och grafteorin började.
En historisk fågelperspektivkarta över Königsberg (Koningsberga), som visar Pregel och ön i hjärtat av de sju broarnas problem. År 1736 visade Leonhard Euler att ingen promenad kunde korsa varje bro exakt en gång, och grafteorin började.
Porträtt av Leonhard Euler
Porträtt av Leonhard Euler

Avstånd, diameter och komplement

Avståndet mellan två hörn är det minsta antalet kanter på en väg mellan dem, och diametern är det största avståndet i grafen; i en graf som inte är sammanhängande är den oändlig. Sociala nätverk har små diametrar, vilket är idén bakom de berömda sex stegen mellan två människor (six degrees of separation). Komplementet till en graf har samma hörn och förbinder precis de par som inte var förbundna. Av en graf och dess komplement är alltid minst en sammanhängande.

Utforska själv

Lekplatsen öppnar med Petersengrafen färgad i tre färger. Klicka på Grader och kontrollera handskakningslemmat, klicka på Bipartit för att se en udda cykel, läs sedan in kuben och se de två sidorna träda fram. Läs in huset och klicka på Eulerväg för att se var strecket måste börja. Rita din egen graf och lägg till en kant i taget: se den kortaste cykeln krympa, diametern minska och det kromatiska talet öka när den sista kanten i en K4 kommer på plats.

Ofta ställda frågor

Vad är skillnaden mellan en väg, en stig och en vandring?

En vandring är vilken följd av hörn förbundna med kanter som helst och får upprepa både hörn och kanter. En stig får upprepa hörn men inte kanter, och därför kan en Eulerväg, som strängt taget är en stig, passera ett hörn flera gånger. En väg upprepar ingetdera.

Vad är fyrfärgssatsen?

Den säger att varje graf som kan ritas på papper utan korsande kanter kan färgas med högst fyra färger, så varje karta klarar sig med fyra. Den bevisades 1976 av Kenneth Appel och Wolfgang Haken med hjälp av en dator, som den första stora satsen som bevisats på det sättet.

Vad är en Hamiltoncykel?

En cykel som besöker varje hörn exakt en gång, i stället för varje kant. Det liknar Eulerfrågan, men inget enkelt test för den är känt: att avgöra om en graf har en sådan är NP-fullständigt. Petersengrafen har en Hamiltonväg men ingen Hamiltoncykel.

Var används grafteori?

Ruttplanerare söker i väggrafer, sökmotorer rangordnar webbsidor efter deras länkar, kompilatorer färgar grafer för att fördela processorregister, scheman undviker krockar genom att färga en graf över konflikter, kemister räknar molekyler som grafer, och nätverk av datorer, kraftledningar och vänner studeras som grafer.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Öppna grafteorins lekplats