Grafteori

Punkter og linjer imellem dem: mere er en graf ikke. Alligevel beskriver det samme billede et vejkort, et netværk af venner, et molekyle og internettet, og de spørgsmål, man kan stille om det, fra hvor mange farver det kræver, til om det kan tegnes i én streg, har holdt matematikere beskæftiget siden 1736.

En graf med ti knuder, Petersen-grafen, hvis knuder er farvet med tre farver, så ingen kant forbinder to knuder med samme farve
En graf med ti knuder, Petersen-grafen, hvis knuder er farvet med tre farver, så ingen kant forbinder to knuder med samme farve

Knuder og kanter

En graf har knuder, også kaldet punkter eller hjørner, og kanter, der hver forbinder to knuder. Hvor knuderne tegnes, er ligegyldigt; det eneste, der tæller, er, hvilke par der er forbundet, så den samme graf kan se meget forskellig ud på papiret. Graferne på legepladsen er simple: ingen kant fra en knude til sig selv og højst én kant mellem to knuder. Med n knuder kan der højst være n(n − 1) / 2 kanter; en graf, der har dem alle, kaldes komplet, og K5 er den komplette graf på fem knuder.

Grader og håndtrykslemmaet

En knudes grad er antallet af kanter, der støder til den. Læg alle graderne sammen, og du får præcis det dobbelte af antallet af kanter, fordi hver kant har to ender og tælles én gang ved hver. Det er håndtrykslemmaet: i enhver gruppe giver håndtrykkene, talt person for person, tilsammen det dobbelte af antallet af håndtryk. Det betyder også, at antallet af knuder med ulige grad altid er lige. En graf, hvor alle knuder har samme grad k, kaldes k-regulær.

Sammenhængende grafer, træer og kredse

En graf er sammenhængende, når man kan komme fra hver knude til alle de andre langs kanterne; ellers falder den fra hinanden i dele, kaldet komponenter. En kreds er en rundtur, der vender tilbage til sit udgangspunkt uden at bruge en knude to gange, og længden af den korteste kreds kaldes grafens talje. En sammenhængende graf uden kredse er et træ, og et træ med n knuder har altid præcis n − 1 kanter: én færre, og det falder fra hinanden, én mere, og det får en kreds. Enhver sammenhængende graf indeholder et udspændende træ, et træ, der når alle knuder og kun bruger nogle af kanterne.

Todelte grafer og farvning

Farv knuderne, så ingen kant forbinder to knuder med samme farve. Det mindste antal farver, der kan klare det, er det kromatiske tal. Én farve er kun nok, hvis der ingen kanter er. To farver er nok, netop når grafen er todelt: dens knuder deler sig i to sider, og hver kant går på tværs. Dénes Kőnig viste i 1936, at det er det samme som ikke at have nogen kreds af ulige længde, fordi en ulige kreds ikke kan skifte mellem to farver hele vejen rundt. For tre eller flere farver kendes ingen tilsvarende enkel test: at afgøre, om tre farver er nok, er NP-fuldstændigt, så programmer må søge, ligesom legepladsen gør.

Et eksempel: Petersen-grafen

Tag en femkant A–B–C–D–E og en femtakket stjerne F–H–J–G–I inden i den, og forbind hvert hjørne af femkanten med en spids af stjernen: A–F, B–G, C–H, D–I og E–J. Det er Petersen-grafen, med 10 knuder og 15 kanter. Hver knude har grad 3, så graderne giver tilsammen 30, det dobbelte af 15. Dens korteste kreds har længde 5, så den har ingen trekant, men femkanten er en ulige kreds, så den er ikke todelt og kræver 3 farver. To vilkårlige knuder ligger højst 2 kanter fra hinanden, så dens diameter er 2. Alle ti grader er ulige, så den har ingen Eulervej, og den kan ikke tegnes uden krydsninger.

Eulerveje og Königsbergs broer

Byen Königsberg havde syv broer, der forbandt fire landområder, og folk spurgte sig selv, om man kunne gå over hver bro præcis én gang. I 1736 viste Leonhard Euler, at det ikke kunne lade sig gøre, og dermed var grafteorien født. Hver gang en gåtur passerer et landområde, bruger den to broer, så kun start og slut må have et ulige antal broer, og alle fire landområder i Königsberg havde et ulige antal. En tur, der bruger hver kant én gang, kaldes nu en Eulervej, eller en Eulerkreds, når den slutter, hvor den begyndte. Carl Hierholzer beviste i 1873, at betingelsen også er tilstrækkelig: hvis alle kanter hænger sammen i ét stykke, og højst to grader er ulige, findes turen, og hans metode, der sætter rundture sammen, bruges stadig til at finde den.

Et historisk fugleperspektivkort over Königsberg (Koningsberga), der viser Pregel og øen i hjertet af de syv broers problem. I 1736 viste Leonhard Euler, at ingen tur kunne krydse hver bro præcis én gang, og grafteorien begyndte.
Et historisk fugleperspektivkort over Königsberg (Koningsberga), der viser Pregel og øen i hjertet af de syv broers problem. I 1736 viste Leonhard Euler, at ingen tur kunne krydse hver bro præcis én gang, og grafteorien begyndte.
Portræt af Leonhard Euler
Portræt af Leonhard Euler

Afstand, diameter og komplement

Afstanden mellem to knuder er det mindste antal kanter på en vej mellem dem, og diameteren er den største afstand i grafen; i en graf, der ikke er sammenhængende, er den uendelig. Sociale netværk har små diametre, og det er idéen bag de berømte seks led mellem to vilkårlige mennesker. Komplementet til en graf har de samme knuder og forbinder netop de par, der ikke var forbundet. Af en graf og dens komplement er mindst én altid sammenhængende.

Udforsk det selv

Legepladsen åbner med Petersen-grafen farvet med tre farver. Klik på Grader, og tjek håndtrykslemmaet, klik på Todelt for at se en ulige kreds, og indlæs så terningen, og se de to sider dukke op. Indlæs huset, og klik på Eulervej for at se, hvor stregen skal begynde. Tegn din egen graf, og tilføj én kant ad gangen: se den korteste kreds blive kortere, diameteren falde og det kromatiske tal stige, når den sidste kant i en K4 kommer på.

Ofte stillede spørgsmål

Hvad er forskellen på en vej, en tur og en vandring?

En vandring er enhver følge af knuder forbundet af kanter og må gentage både knuder og kanter. En tur må gentage knuder, men ikke kanter, og derfor kan en Eulervej, som strengt taget er en tur, passere en knude flere gange. En vej gentager ingen af delene.

Hvad er firefarvesætningen?

Den siger, at enhver graf, der kan tegnes på papir uden krydsende kanter, kan farves med højst fire farver, så ethvert landkort kan nøjes med fire farver. Den blev bevist i 1976 af Kenneth Appel og Wolfgang Haken ved hjælp af en computer, som den første store sætning, der blev bevist på den måde.

Hvad er en Hamiltonkreds?

En kreds, der besøger hver knude præcis én gang, i stedet for hver kant. Det ligner Euler-spørgsmålet, men der kendes ingen enkel test for det: at afgøre, om en graf har en, er NP-fuldstændigt. Petersen-grafen har en Hamiltonvej, men ingen Hamiltonkreds.

Hvor bruges grafteori?

Ruteplanlæggere søger i vejgrafer, søgemaskiner rangerer websider efter deres links, compilere farver grafer for at fordele processorregistre, skemaer undgår sammenfald ved at farve en graf over konflikter, kemikere tæller molekyler som grafer, og netværk af computere, elledninger og venner studeres som grafer.

Er du klar til at prøve?

Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.

Åbn grafteori-legepladsen