Graph

•Graph G(V, E) - Graph aus Knoten- und Kantenmenge V + E
•Knoten v(ertex) - (v ∈ V)
•Kante e(dge) - (e ∈ E)

ungerichteter Graph (i-j)

E ⊆ { {i,j} : i ∈ V, j ∈ V, i ≠ j }

gerichteter Graph (i->j)

E ⊆ { (i,j) : i ∈ V, j ∈ V }

Nachbarschaft/adjeszenz

G = (V, E): gerichteter Graph.
• i, j ∈ V Kante verläuft zwischen 2 benachbarten Knoten: (i, j) ∈ E ∨ (j, i) ∈ E.
•Schleife : Kante (i, i)(identischer Ausgangs- und Endknoten)

Grad

GradG(v) = |{e(i, j) ∈ E : v = i ∨ v = j}|
Da jede Kante genau zwei Knoten verbindet ist die Summe aller Knotengrade = 2∗|E|(Anzahl der Kanten)

Eingangsgrad

GradIN(v) = |{e(i, j) ∈ V : v = j}|

Ausgangsgrad

GradOUT(v) = |{e(i, j) ∈ V : v = i}|

Darstellung

Abstrakt

Sei G1(V1, E1)
•V1 = {a, b, c, d}
•E1 = { (a,b), (a,c), (a,d), (b,b), (b,c), (d,b), (d,c) }

graphisch

Adjazenzliste

Adjazenzmatrix

Weg

Weg in G: Tupel (v0, v1, ..., vk), so dass für alle i mit 0 ≤ i < k gilt:
•(vi, vi+1) ∈ E für gerichtete Graphen
•{vi, vi+1} ∈ E für ungerichtete Graphen
Das Tupel (v0, v1, ..., vk) wird dann ein Weg von v0 nach vk
genannt. k ist die Länge des Weges. k gibt also an, wie viele Kanten auf dem Weg durchlaufen werden.

einfach

kein Knoten kommt mehr als einmal im Weg vor
einfacher Kreis: keine Kante wird mehrfach durchlaufen +kein Knoten kommt mehr als einmal vor(außer Start- und Endknoten )

azyklisch

Ein Graph heißt azyklisch, falls er keinen einfachen Kreis enthält.

zusammenhängend

ungerichteter Graph
G ist zusammenhängend, wenn für alle Knoten v, w ∈ V gilt: Es gibt einen Weg von v nach w.

stark zusammenhängend

gerichteter Graph
G ist stark zusammenhängend, wenn für alle Knoten v, w ∈ V gilt: Es gibt einen Weg von v nach w.

Hamilton

Weg

Ein Weg W = (v0, ..., vk) ist ein Hamilton-Weg wenn jeder Knoten aus V genau einmal in W vorkommt

Kreis

Ein Weg W = (v0, ..., vk) ist ein Hamilton-Kreis wenn k > 1 und v0 = vk und (v0, ..., vk-1) ein Hamilton-Weg ist

Euler

ungerichteter Graph

Weg

Ein Weg W = (v0, ..., vk) ist ein Euler-Weg wenn jede Kante aus E genau einmal durchlaufen wird. D.h. für jedes e ∈ E genau ein i ∈ {0, ..., k−1} gibt, so dass e = {vi, vi+1}

Kreis

Ein Weg W = (v0, ..., vk) ist ein Euler-Kreis wenn W ein Euler-Weg ist und v0 = vk.

Satz über die Existenz von Euler-Kreisen und Euler-Wegen

G = (V, E): ungerichtet, zusammenhängend
a) Euler-Kreis gdw. jeder Knoten von G einen geraden Grad besitzt
b) Euler-Weg gdw. es in G genau zwei Knoten mit ungeraden Grad gibt.

isomorph

G1= (V1, E1) + G2= (V2, E2) sind isomorph, wenn sie sich höchstens in der Bezeichnung ihrer Knoten unterscheiden, ansonsten aber die selbe Struktur haben.

bijektive Funktion

f: V1⟶V2 existieren, mit den Eigenschaften:
•falls G1 und G2 gerichtete Graphen sind:
(u, v) ∈ E1 ⟷ (f(u), f(v)) ∈ E2
•falls G1 und G2 ungerichtete Graphen sind:
{u, v} ∈ E1 ⟷ {f(u), f(v)} ∈ E2

planar

wenn sich in der graphischen Darstellung keine zwei Kanten überkreuzen

gewichtet

eine Funktion, welche jeder Kante in G eine reelle Zahl (das Gewicht) zuordnet.
d: E ⟶ ℝ

Bäume

ungerichteter Baum B

B ist ein ungerichteter, zusammenhängender Graph G = (V, E), der keinen einfachen Kreis enthält.

Eigenschaften:

• Es existiert genau ein einfacher Weg, der die Knoten x und y verbindet.
• Die äußeren Knoten v ∈ V, mit Grad(v) ≤ 1 heißen Blätter.
• Ist B endlich und V ≠ ∅ so gilt: |E| = |V| − 1

Spannbäume

Ein ungerichteter Baum B = (V', E') heißt Spannbaum von G, wenn V' = V und E' ⊆ E ist.

Algorithmus von Kruskal

1. Erstelle eine Liste aller Kanten in G mit ihren dazugehörigen Gewichten.
2. Sortiere die Liste nach Kantengewicht in aufsteigender Reihenfolge.
3. Jeder Knoten v ∈ V beginnt als eigenständiger Baum.
4. Solange Kanten in der sortierten Liste enthalten sind und noch nicht alle Knoten verbunden sind wiederhole:
   • Entferne die Kante mit dem geringsten Gewicht aus der Liste.
   • Wenn die Kante zwei nicht verbundene Bäume verbindet füge diese mit der Kante zu einem Baum zusammen.

Algorithmus von Prim

1. Beginne bei einem beliebigen Knoten v ∈ V aus G.
2. Wiederhole so lange noch nicht alle Knoten verbunden wurden:
   • Betrachte alle Kanten von Knoten im Ergebnisbaum, zu den Knoten, die noch nicht verbunden wurden.
   • Wähle die Kante mit dem geringsten Gewicht und nehme diese und den verbundenen Knoten in den Baum auf.

gerichteter Baum

“Wurzel” auswählt und alle Kanten in die Richtung orientiert, die von der Wurzel weg führt

Eigenschaften gerichtete Bäume

• Für jeden Knoten v ∈ V gilt: Es gibt in B genau einen Weg von der Wurzel zum Knoten v.
• Für jeden Knoten v ∈ V gilt: GradIN(v) ≤ 1
• Diejenigen Knoten v ∈ V, mit GradOUT(v) = 0, heißen Blätter.
• Jeder gerichtete Baum ist ein gerichteter azyklischer Graph (aber nicht umgekehrt!)

rekursive Definition

man kann gerichtete Bäume mit einem weiteren Knoten (-> neue Wurzel) zusammenschließen zu neuem gerichtetem Baum

Binärbaum

vollständiger Binärbaum

Ein Binärbaum B = (V, E) heißt vollständiger Binärbaum falls gilt:
•jeden Knoten v ∈ V, der kein Blatt ist, gilt: GradOUT(v) = 2
•Es gibt eine Zahl h ∈ ℕ, so dass für jedes Blatt v ∈ V
gilt: Der Weg von der Wurzel zum Blatt v hat die Länge h
•Ist B ein vollständiger Binärbaum hat bei einer Höhe von h genau 2h Blätter und 2h+1 - 1 Knoten

Huffman-Codierung

1. Zeichen nach ordnen nach Häufigkeit ihrers Auftauchens
   • Abra kadabra (A: 5, b:2, k:1, r:1)
2. Einen Baum starten mit der kleinsten Anzahl
3. weiter zusammenbauen mit jeweils der nächst kleineren Anzahl
4. Ast links ist 0, Ast rechts ist 1 -> so einfach codiert verschickbar. (Baum muss mitgeschickt werden)