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)

IT – Bäume

Allgemeines

  • Kante, die von Knoten A nach Knoten B geht
  • A – Vater ( Vorgänger, parent )
  • B – Sohn ( Kind, child )
  • Zwei Knoten vom selben Vater – Brüder ( siblings, Geschwister )
  • Grad eines Knotens – Anzahl direkter Nachfolger
  • Grad eines Baumes – max. Knotengrad aller Knoten
  • Blätter – Knoten vom Grad 0
  • innere Knoten Grad > 0
  • jeder Knoten hat genau 1 Vorgänger
  • Stufe eines Knotens – Pfadlänge von der Wurzel
    Wurzel – Stufe 0
    Knoten – Stufe des direkten Vorgängers K + 1
  • Höhe h – max. Stufen der Baumknoten + 1
  • Gewicht w – Anzahl aller Blätter
  • Menge mehrerer Bäume – Wald

Wurzel W
Blätter G, B, A, L, Q, F, I
Innere Knoten G, B, W
Höhe max. Stufe + 1, h = 4

Binärbaum

  • endliche Menge von Elementen
  • ist entweder leer oder hat ausgezeichnetes Element (Wurzel)
  • außerdem
    • übrige Elemente in 2 disjunkte Untermengen zerlegbar
    • Untermengen sind selbst Binärbäume

 

Binärbäume mit disjunkten Untermengen

 

links iO – rechts nicht iO, da B weder als linkes noch als rechtes Kind erkennbar ist

 

Untermengen sind nicht disjunkt
B und C haben gleiche Untermenge E

 

 

Spezielle Binärbäume

  • ähnlich – selbe Struktur
  • äquivalent – selbe Struktur und selbe Information
  • vollständig
    • jeder Knoten der Stufe h-1 ist ein Blatt
    • jeder Knoten der Stufe < h-1 hat nicht leere linke und rechte Unterbäume
  • max. Anzahl Knoten auf Stufe k ist 2k ( 0 ≤ k ≤ h – 1 )
  • max. Anzahl Knoten bei Höhe h ist 2h– 1 ( h ≥ 1 )
  • strikt – jeder innere Knoten besitzt nicht-leere linke & rechte Unterbäume
  • ausgeglichen, wenn für alle k ≥ 0 gilt:
    • jedes Blatt ist auf Stufe k oder k + 1
    • jeder Knoten auf Stufe < k hat nicht-leere linke & rechte Unterbäume
  • fast vollständig, wenn für für alle k ≥ 0 gilt:
    • jedes Blatt ist auf Stufe k oder k + 1
    • jeder Knoten auf Stufe < k hat nicht-leere linke & rechte Unterbäume
    • falls innerer Knoten Nachfolger (nicht direkter Nachfolger) auf Stufe k + 1 besitzt,
      dann ist linker Unterbaum vollständig mit Blättern Stufe k + 1

 

strikt
ausgeglichen

 

ausgeglichen

 

strikt
ausgeglichen
fast vollständig