IT – Graphentheorie

Definition

G = ( V, E ) → gerichteter Graph (Digraph) ↔

  • V ≠ Ø – Knotenmenge
    v ∈ V – Knoten / Vertex
  • E ⊆ V²  – Kantenmenge
    e = { u, v } ∈ E – Kante
    u – Quelle, v – Ziel der Kante
  • e = ( u, v ) ∈ E mit u = v – Schlinge

G = ( V, E )  → ungerichteter Graph ↔

  • V ≠ Ø – Knotenmenge
  • E ⊆ V²  – Kantenmenge
  • 2 Knoten heißen benachbart ↔ { u, v }  ∈ E

allgemein:

  • bestehen aus Knoten und sie verbindende Kanten
  • Kanten mit Orientierung: gerichtete Graphen
  • Kanten ohne Orientierung: ungerichtete Graphen

Kantenzug ( walk ) – Länge n von v0 nach vn

  • für alle i ∈ { 0, … , n – 1 } gilt: { vi, vi+1 }  ∈ E
  • gerichtet: v0 Startknoten, vn Endknoten von k
  • ungerichtet: vo, vn Endknoten von k
  • v1, … , vn-1 – innere Knoten von k
  • v 0 = vngeschlossener Kantenzug ( closed walk )

Weg ( trail )

  • k ist ein Kantenzug
  • für alle  i, j ∈ { 0, … , n – 1 } mit i ≠ j gilt:  { vi, vi+1 } ≠ { vj, vj+1 }
  • keine Kante doppelt, ggfs. Kreuzungen

Einfacher Weg oder Pfad ( path )

  • k ist ein Weg
  • für alle i, j ∈ { 0, … , n } mit  i ≠ j gilt: vi ≠ vj
  • keine Knoten doppelt, keine Kreuzungen

Kreis ( closed trail ) 

  • k ist ein Weg
  • v0 = vn
  • Graph ohne Kreis = kreisfrei
  • erster und letzter Knoten sind gleich, ggfs. Kreuzungen

Einfacher Kreis ( cycle )

  • k‘ ist ein einfacher Weg
  • v0 = vn
  • Graph ohne Zyklus = azyklisch
  • erster und letzter Knoten gleich, keine Kreuzungen

 Zusammenhängend ( connected )

  •  für alle u, v  ∈ V, u  ≠ v gilt:
  • Kantenzug k = ( vo , … , vn )  ∈ Vn+1 
  • mit vo = u und  vn = v

weiteres unter Bäume (ungerichteter, azyklischer, zusammenhängender Graph)

Kommentar verfassen