Grafteori

Fra Wikipedia, den frie encyklopædi

Graf med 6 knuder (punkter) og 7 kanter
Graf med 6 knuder (punkter) og 7 kanter

Grafteori er studiet af grafer og problemer der kan reduceres til grafer og er i dette sammenhæng både et område indenfor 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 rafer af stor betydning indenfor kompleksitetsteorien.

En graf kan i dette 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.

Indholdsfortegnelse

[redigér] Definitioner

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

  • en mængde V af knuder,
  • en mængde EV(2) af uordnede par af knuder i V kaldet kanter.

Læg mærke til, at denne definition ikke tillader loop (kanter fra en knude til sig selv) eller dobbeltkanter (2 eller flere kanter mellem de samme to knuder). En sådan graf kaldes under tiden for en simpel graf, og en graf, hvor man man tillader loop og dobbeltkanter, kaldes under tiden 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 i en graf er en følge (v1, v2, ..., vn) af knuder i V, så {vi, vi+1} ∈ E for alle 1 ≤ i < n.

En cykel eller kreds er en sti (v1, v2, ..., vn), så vivj for ij og {vn, v1} ∈ E.

En graf G = (V, E) kaldes

  • komplet, hvis E = V(2), dvs. der er kanter mellem alle knuder,
  • sammenhængende, hvis der findes en sti mellem alle knuder, eller med andre ord: for alle v, wV skal der findes en sti (v1, v2, ..., vn), så v = v1 og w = vn,
  • todelt, hvis kanterne V kan deles op i to disjunkte mængder V = XY, XY = Ø, så alle kanter går mellem de to dele af grafen, eX og eY for alle eE.
  • en plangraf, hvis den kan indlejres i planet (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 orienteret 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 EV 2 af ordnede par af knuder også kaldet kanter.

I en orienteret graf tegnes kanterne med pile, så man kan se hvor kanterne begynder og ender.

[redigér] Historie

Grafteorien rækker tilbage til året 1736 da Leonard Euler publicerede en løsning for Köningsberg broproblemet, som består af at bestemme, om det er muligt at krydse alle syv broer over floden Pregel i det daværende Kaliningrad 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 umuligt. I dette sammenhæng brugte han metoder der i dag ville falkde 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.

[redigér] Problemer

Den handelsrejsendes problem (eng: Travelling Salesman Problem, TSP).

[redigér] Vigtige begreber

Kant, vej, punkt, todelt graf, Hamiltonkreds

organisation