Grafteori

Fra Wikipedia, den frie encyklopædi

Du har nye beskeder (forskel fra næstsidste redigering).

Graf med 6 knuder (punkter) og 7 kanter

Grafteori er studiet af grafer og problemer der kan reduceres til grafer. Blandt disse kan nævnes skemalægning, ruteproblemer, jobtilordning, tegning af figurer i én streg, lineær programmering.

En graf er i denne sammenhæng 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.

[redigér] Definitioner

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

en mængde V af knuder,
en mængde E ⊆ V⁽²⁾ 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 (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.

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 kanterne V kan deles op i to disjunkte mængder 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 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.