Grafteori og grafer: definition, grundbegreber og anvendelser

Grafteori er et område af matematikken om grafer. En graf er en abstrakt repræsentation af: et antal punkter, der er forbundet med linjer. Hvert punkt kaldes normalt et toppunkt (flere punkter kaldes toppunkter), og linjerne kaldes kanter. Grafer er et værktøj til at modellere relationer. De bruges til at finde svar på en række problemer.

Nogle af disse spørgsmål er:

• Hvordan finder man den korteste vej mellem to steder?
• Er et netværk sammenhængende, eller består det af adskilte komponenter?
• Kan man planlægge ruter, farve noder, eller matche par af elementer optimalt?
• Hvornår findes der en cyklus, og hvordan identificeres specielle typer som Euler- eller Hamilton-cyklusser?
• Hvordan repræsenterer og analyserer man komplekse netværk som sociale netværk eller transportsystemer?

Grundlæggende begreber

• Toppunkter (noder): De enkelte punkter i grafen. Ofte betegnet med bogstaver eller tal.
• Kanter: Forbindelser mellem to toppunkter. Kan være rettede eller urettede.
• Urettet graf: Kanter har ingen retning; forbindelsen går begge veje.
• Rettet graf (digraf): Hver kant har en retning fra et toppunkt til et andet.
• Vægtede grafer: Kanter bærer en vægt (fx afstand, omkostning eller tid).
• Enkel graf, multigraf og løkker: En enkel graf har højst én kant mellem to noder og ingen løkker (kanter fra en node til sig selv). Multigrafer kan have parallelle kanter; løkker forbinder en node med sig selv.
• Grad: Antallet af kanter der mødes i et toppunkt (i rettede grafer skelnes mellem indgrad og udgrad).
• Sti, gang, spor og cyklus: En sti er en sekvens af kanter uden gentagne noder; en cyklus leder tilbage til udgangsnoden.
• Sammenhæng og komponenter: En graf er sammenhængende, hvis der findes sti mellem alle par af noder. En komponent er en sammenhængende del af grafen.
• Træer og skove: Et træ er en sammenhængende, acyklisk urettet graf. En skov er en samling af træer.
• Bipartite grafer: Noder kan opdeles i to sæt, så alle kanter går mellem de to sæt — nyttigt ved matching-problemer.
• Planaritet: En graf er planær, hvis den kan tegnes i planen uden krydsende kanter.

Repræsentation i computere

• Adjacensmatrix: En kvadratisk matrix hvor en celle angiver om der er kant mellem to noder (praktisk for tætte grafer).
• Adjacensliste: For hver node en liste over naboer (pladsbesparende for sparsomme grafer).
• Edge-list: En simpel liste af kanter; let at opbevare og gennemløbe.

Valget af repræsentation påvirker algoritmers hukommelsesforbrug og køretid.

Vigtige algoritmer og teoretiske problemer

• BFS (Breadth-First Search): Finder korteste antal kanter mellem to noder i urettede eller ensartede vægtede grafer.
• DFS (Depth-First Search): Bruges til at finde komponenter, cyklusser, og udføre topologisk sortering.
• Dijkstra: Korteste vej i vægtede grafer med ikke-negative vægte.
• Bellman–Ford: Korteste vej også med negative vægte (kan detektere negative cyklusser).
• Floyd–Warshall: All-pairs shortest paths (praktisk i mindre grafer).
• Prim og Kruskal: Algoritmer til minimum spændende træ (MST) i vægtede urettede grafer.
• Ford–Fulkerson / Edmonds–Karp: Algoritmer for maks. flow og min-cut i netværk.
• Matching-algoritmer: Fx Hopcroft–Karp for bipartite matching; vigtige i opgaver med parringer.
• NP-komplekse problemer: Mange centrale problemer som graf-farvning, Hamilton-cyklus, klik og vertex cover er NP-hårde eller NP-komplette.
• Graph isomorphism: At afgøre om to grafer er strukturelt ens — et interessant problem i kompleksitetsteori.

Anvendelser

• Netværk: Internetstruktur, routing, netværkssikkerhed og kommunikationsprotokoller.
• Transport og logistik: Ruteplanlægning, tidsplaner, optimering af leveringsnetværk.
• Sociale netværk: Analyse af forbindelser, centralitet, fællesskaber og informationstilgang.
• Biologi og medicin: Proteinnetværk, genregulering og spredning af sygdomme.
• Kemi: Molekylstruktur og bindingsnetværk.
• Planlægning og scheduling: Opgaveafhængigheder og ressourcetildeling.
• Database- og semantiske netværk: Relationer mellem dataobjekter og søgning i store grafdatabaser.
• Computer science: Compiler-optimeringer (fx register allocation), kredsløbsanalyse, og billedbehandling.

Historie og videre perspektiver

Grafteoriens begyndelse tilskrives ofte Leonhard Euler og hans løsning af Königsberg bro-problemet i 1736. Siden er området vokset kraftigt og spiller i dag en central rolle både i teoretisk matematik og i mange praktiske anvendelser inden for datalogi, ingeniørarbejde, biologi og samfundsvidenskab. Moderne forskning omfatter store netværk (big data), dynamiske og tilfældige grafer, spektral grafteori og anvendelser i maskinlæring.

For at komme videre kan man se på konkrete eksempler (tegn simple grafer og prøv BFS/DFS), eksperimentere med repræsentationer i kode (adjacensliste vs. matrix) og studere klassiske algoritmer og deres køretidsanalyser.

Forskellige former for grafer

• Grafteori har mange aspekter. Grafer kan være dirigerede eller udirigerede. Et eksempel på en rettet graf er et vejsystem i en by. Nogle gader i byen er ensrettede gader. Det betyder, at der på disse strækninger kun er én retning at følge.
• Grafer kan være vægtede. Et eksempel er et vejnet med afstande eller med vejafgifter (for veje).
• Knuderne (cirklerne i skemaet) i en graf kaldes hjørner. De linjer, der forbinder knuderne, kaldes kanter. Der kan ikke være nogen linje mellem to knudepunkter, der kan være én linje, eller der kan være flere linjer.
• Inden for grafteori er strukturer i form af træer meget udbredte, de repræsenterer hierarkiske strukturer. Et træ er en rettet eller urettet graf, hvor der ikke er nogen cyklus, dvs. ingen mulighed for at gå fra et toppunkt (f.eks. en by) til det samme ved hjælp af hver kant, som man kun bruger én gang (man går kun én gang på hver vej, man tager).

 
En rettet graf.  

Historie

→ →

En visualisering af de syv broer i Königberg. Leonhard Euler løste dette problem i 1736, hvilket førte til udviklingen af topologi og moderne grafteori.

En graf er en abstrakt datastruktur. Den indeholder knuder, der normalt er relateret til hinanden. En knude er et datasæt, typisk i form af ordnede par. Knuder er enten forbundet eller ikke forbundet med en anden knude. Relationen mellem knuder defineres normalt som en kant. Grafer er nyttige på grund af deres evne til at forbinde knuder med andre knuder. Der findes et par repræsentationer af grafer i praksis.

Leonhard Euler boede i en by ved navn Königsberg. (Dens navn blev ændret til Kaliningrad i 1946). Byen ligger ved floden Pregel. Der er en ø i floden. Der er nogle broer over floden. Euler ville gerne gå rundt og bruge hver af broerne én gang. Han spurgte, om han kunne gøre dette. I 1736 udgav han en videnskabelig artikel, hvor han viste, at det ikke var muligt. I dag er dette problem kendt som de syv broer i Königsberg. Artiklen betragtes som den første artikel i grafteoriens historie.

Denne artikel, såvel som Vandermondes artikel om ridderproblemet, videreførte den analyse situs, som Leibniz havde indledt. Eulers formel var om antallet af kanter, hjørner og flader i et konvekst polyeder blev studeret og generaliseret af Cauchy og L'Huillier, og den ligger til grund for topologien.

Fusionen af ideer fra matematikken med ideer fra kemien er oprindelsen til en del af standardterminologien i grafteori. Især blev begrebet "graf" indført af Sylvester i en artikel offentliggjort i 1878 i Nature.

Et af de mest berømte og produktive problemer inden for grafteori er firefarveproblemet: "Er det sandt, at ethvert kort tegnet i planen kan have sine regioner farvet med fire farver på en sådan måde, at to regioner, der har en fælles grænse, har forskellige farver?"

 
Problemet med Königsbergbroen, på et bykort  


Samme problem, men ved hjælp af en graf  

Spørgsmål og svar

Spørgsmål: Hvad er grafteori?

Spørgsmål: Hvad kaldes punkterne i en graf?

Sp: Hvad repræsenterer linjerne mellem toppene?

Spørgsmål: Hvordan kan grafer bruges?

Sp: Hvilke spørgsmål kan grafer hjælpe med at besvare?

Spørgsmål: Er der forskellige typer grafer?

Spørgsmål: Findes der software til at arbejde med grafteori?

Søg efter bogstav