Grafteori

Disambig bordered fade.svg For alternative betydninger, se Graf (flertydig).
Disambig bordered fade.svg For alternative betydninger, se Knude (flertydig).
Disambig bordered fade.svg For alternative betydninger, se Punkt (flertydig).
Graf med 6 knuder (punkter) og 7 kanter

Grafteori er studiet af grafer og problemer, der kan reduceres til 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 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 loops (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.

Antallet af kanter fra en knude, kaldes dens valens.


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 mængden af knuder V kan deles op i to disjunkte mængder X og Y, (dvs. 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 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 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 ² 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.

Andre sprog
አማርኛ: ሥነ ግራፍ
беларуская: Тэорыя графаў
čeština: Teorie grafů
Ελληνικά: Θεωρία γράφων
English: Graph theory
Esperanto: Grafeteorio
euskara: Grafo teoria
Bahasa Indonesia: Teori graf
íslenska: Netafræði
日本語: グラフ理論
한국어: 그래프 이론
lietuvių: Grafų teorija
latviešu: Grafu teorija
монгол: Графын онол
Bahasa Melayu: Teori graf
Nederlands: Grafentheorie
norsk nynorsk: Grafteori
norsk: Grafteori
português: Teoria dos grafos
sicilianu: Tiuria dî grafi
srpskohrvatski / српскохрватски: Teorija grafova
Simple English: Graph theory
slovenčina: Teória grafov
slovenščina: Teorija grafov
српски / srpski: Теорија графова
svenska: Grafteori
Türkçe: Çizge teorisi
українська: Теорія графів
Tiếng Việt: Lý thuyết đồ thị
中文: 图论
粵語: 圖論