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.