Grafteori

For alternative betydninger, se Graf (flertydig).

For alternative betydninger, se Knude (flertydig).

For alternative betydninger, se Punkt (flertydig).

Grafteori er studiet af grafer og problemer, der kan reduceres til kombinatoriske grafer, og er i denne sammenhæng både et område inden for diskret matematik og et vigtigt hjælpemiddel i datalogien, hvor den kan bruges til at løse mange opgaver, såsom skemalægning, rutefinding, jobtilordning, tegning af figurer i én streg og lineær programmering. Desuden er grafer af stor betydning inden for kompleksitetsteorien.

En graf kan i denne sammenhæng illustreres ved et diagram bestående af et antal punkter (knuder) forbundet med et antal kanter. Hver kant illustreres som et linjestykke (eller kurvestykke) med knuder som sine to endepunkter.

Definitioner

En graf eller urettet graf G er et par (V, E) bestående af

en mængde V af knuder, (også kaldt hjørner eller punkter).
en mængde E ⊆ V⁽²⁾ af uordnede par af knuder i V kaldet kanter.

Læg mærke til, at denne definition ikke tillader løkker (kanter fra en knude til sig selv) eller dobbeltkanter (2 eller flere kanter mellem de samme to knuder). En sådan graf kaldes sommetider for en simpel graf. En graf med løkker og dobbeltkanter kaldes sommetider en pseudograf.

Grafen på billedet består af

V = { 1, 2, 3, 4, 5, 6 },
E = { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} }.

En sti (eller vej) i en graf er en følge (v₁, v₂, ..., v_n) af knuder i V, så {v_i, v_i+1} ∈ E for alle 1 ≤ i < n.

En cykel eller kreds er en sti (v₁, v₂, ..., v_n), så v_i ≠ v_j for i ≠ j og {v_n, v₁} ∈ E.

Antallet af kanter fra en knude kaldes dens valens eller grad. En graf G = (V, E) kaldes

komplet, hvis E = V⁽²⁾, dvs. der er kanter mellem alle knuder,
sammenhængende, hvis der findes en sti mellem alle knuder, eller med andre ord: for alle v, w ∈ V skal der findes en sti (v₁, v₂, ..., v_n), så v = v₁ og w = v_n,
todelt, hvis mængden af knuder V kan deles op i to disjunkte mængder X og Y, (dvs. V = X ∪ Y, X ∩ Y = Ø), så alle kanter går mellem de to dele af grafen, e ⊄ X og e ⊄ Y for alle e ∈ E.
en plangraf, hvis den kan indlejres i planen (tegnes på et stykke papir), så ingen kanter krydser hinanden,
en skov, hvis der ikke findes cykler i grafen, der går igennem flere end 2 knuder,
et træ, hvis det er en sammenhængende skov.

En rettet graf (evt. digraf efter det engelske digraph – directed graph) G er at par (V, E) bestående af

en mængde V af knuder,
en mængde E ⊆ V² af ordnede par af knuder også kaldet kanter.

I en rettet graf tegnes kanterne ofte med pile, så man kan se, hvor kanterne begynder og ender. En rettet graf kaldes orienteret, hvis der mellem hvert knudepar højst findes én kant; med andre ord fremkommer en orienteret graf fra en simpel, urettet graf ved at vælge en retning for hver kant. En orienteret graf er en turnering, hvis den indeholder en (rettet) kant mellem hvert par af knuder.

Historie

Grafteorien rækker tilbage til året 1736, da Leonhard Euler publicerede en løsning for Königsbergs broproblem, som består af at bestemme, om det er muligt at krydse alle syv broer over floden Pregel i det daværende Königsberg uden at krydse en bro dobbelt. Euler formåede at beskrive en nødvendig betingelse for en sådan rute og kunne på denne måde bevise, at en sådan rute er umulig. I denne sammenhæng brugte han metoder, der i dag ville falde under grafteorien.

Selve betegnelsen grafteori blev for første gang i 1878 brugt af Sylvester, og den første lærebog udkom i 1936 af Dénes König. Gennem datalogiens voksende betydning i anden halvdel af det tyvende århundrede har grafteorien i de sidste årtier for alvor fået stor betydning, men indeholder stadigvæk mange uløste problemer.

Problemer

Den handelsrejsendes problem (eng: Travelling Salesman Problem, TSP).
Königsberg broproblem (Eulergrafer)

Se også