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
- Erstelle eine Liste aller Kanten in G mit ihren dazugehörigen Gewichten.
- Sortiere die Liste nach Kantengewicht in aufsteigender Reihenfolge.
- Jeder Knoten v ∈ V beginnt als eigenständiger Baum.
- 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
- Beginne bei einem beliebigen Knoten v ∈ V aus G.
- 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
- Zeichen nach ordnen nach Häufigkeit ihrers Auftauchens
- Abra kadabra (A: 5, b:2, k:1, r:1)
- Einen Baum starten mit der kleinsten Anzahl
- weiter zusammenbauen mit jeweils der nächst kleineren Anzahl
- Ast links ist 0, Ast rechts ist 1 -> so einfach codiert verschickbar. (Baum muss mitgeschickt werden)
Top comments (0)