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 v₀ nach v_n

• für alle i ∈ { 0, … , n – 1 } gilt: { v_i, v_i+1 }  ∈ E
• gerichtet: v₀ Startknoten, v_n Endknoten von k
• ungerichtet: v_o, v_n Endknoten von k
• v₁, … , v_n-1 – innere Knoten von k
• v 0 = v_n – geschlossener Kantenzug ( closed walk )

Weg ( trail )

• k ist ein Kantenzug
• für alle  i, j ∈ { 0, … , n – 1 } mit i ≠ j gilt:  { v_i, v_i+1 } ≠ { v_j, v_j+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: v_i ≠ v_j
• keine Knoten doppelt, keine Kreuzungen

Kreis ( closed trail ) 

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

Einfacher Kreis ( cycle )

• k‘ ist ein einfacher Weg
• v₀ = v_n
• 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 = ( v_o , … , v_n )  ∈ Vⁿ⁺¹ 
• mit v_o = u und  v_n = v

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

Related Images: