Graphen Cheat Sheet
Published: 2021-11-26 11:14:58

#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
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j078ifldmcqfa3g0p8l4.png)
###Adjazenzliste
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jkral7w214dx1zdl1mci.png) 
###Adjazenzmatrix 
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9spa673cvpwebywgqy0p.png)

###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
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/oyi0auibvja0h01razkb.png)

##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.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w2cfx349ci3a8jn95qk4.png)

###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 
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ktrd3cmp558h5mzvtb5c.png)
 
###Binärbaum
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8t3845gtn886mvelyfcf.png)
 
####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)