Title: ADM: Diskrete Mathematik (Graphentheorie)

FrontText: gerichtete Kante
ungerichtete Kante
BackText: ein geordnetes Paar e = (v₁, v₂) von zwei Knoten
ein ungeordnetes Paar e = {v₁, v₂} von zwei Knoten

FrontText: gerichteter Graph
ungerichteter Graph
BackText: Sind alle Kanten e ∈ E(G) gerichtet, so heißt G gerichteter Graph.
Sind alle Kanten e ∈ E(G) ungerichtet, so heißt G ungerichteter Graph.

FrontText: Schlinge
BackText: Eine Kante mit der Form (v,v) (bzw. {v, v}= {v}= vv) heißt Schlinge.

FrontText: adjazent
BackText: Sind zwei Knoten v, w eines Graphen durch eine Kante verbunden, so heißen v und w auch adjazent.

FrontText: Mehrfachkante
BackText: Zu einer Mehrfachkante oder Multikante fasst man in der Graphentheorie eine Menge von Kanten zusammen die zwischen den selben Knoten verlaufen und in gerichteten Graphen zusätzlich identische Orientierung besitzen.

FrontText: schlichter (einfacher) Graph
BackText: Ein Graph G (V, E) heißt schlicht oder einfach, wenn G keine Schlingen und keine Mehrfachkanten enthält.

FrontText: Nachbarn
Knotengrad
BackText: In einem schlichten ungerichteten Graphen G heißen die zu v ∈ V (G) adjazenten Knoten Nachbarn von v.
Die Anzahl der Nachbarn von v ∈ V (G) ist der Knotengrad von v ∈ V (G).

FrontText: Nachfolger
Vorgänger
BackText: In einem gerichteten Graphen:
Nachfolger=Γ+(v)={w∈V :(v,w)∈E}
Vorgänger=Γ−(v)={w∈V :(w,v)∈E}

FrontText: Weggrad
Hingrad
BackText: Die Anzahl der Nachfolger von v∈V(G) ist der Weggrad von v, also die Anzahl der Kanten, die von v
wegführen.
|Γ+(v)| = d+(v)
Die Anzahl der Vorgänger von v∈V(G) ist der Hingrad von v, also die Anzahl der Kanten, die zu v
hinführen.
|Γ−(v)| = d−(v)

FrontText: Handschlaglemma für einen schlichten ungerichteten Graphen G

FrontText: Handschlaglemma für einen gerichteten Graphen G

FrontText: Teilgraph
induzierter Teilgraph.
BackText: Ein Graph G' = (V', E') heißt Teilgraph eines Graphen G = (V, E) wenn V' ⊆ V und E' ⊆ E gelten.
Ein Teilgraph G' = (V', E') eines Graphen G = (V, E) heißt induzierter Teilgraph, wenn E' alle Kanten aus E enthält, für die Anfangs- und Endknoten in V' liegen. d.h., E' muss nicht extra angegeben werden, sondern wird durch Vorgabe von G und V' induziert.

FrontText: Kantenfolge
BackText: Folge von Kanten, wobei der Endknoten immer der Anfangsknoten der darauffolgenden Kante ist.

FrontText: Kantenzug
BackText: Folge von Kanten in einem gerichteten Graphen, wobei der Endknoten immer der Anfangsknoten der darauffolgenden Kante ist.

FrontText: Weg
BackText: Eine Kantenfolge, in der keine Knoten und keine Kanten mehrfach vorkommen.

FrontText: Bahn
BackText: Ein Kantenzug, in dem keine Knoten und keine Kanten mehrfach vorkommen.

FrontText: Kreis
BackText: Eine Kantenfolge, in der keine Knoten und keine Kanten mehrfach vorkommen, mit Anfangspunkt = Endpunkt.

FrontText: Zyklus
BackText: Eine Kantenzug, in dem keine Knoten und keine Kanten mehrfach vorkommen, mit Anfangspunkt = Endpunkt.

FrontText: zusammenhängender ungerichteter Graph
BackText: Ein ungetichteter Graph G heißt zusammenhängend, wenn es zwischen je zwei Knoten v, w ∈ V (G) eine Kantenfolge von v nach w gibt.

FrontText: stark zusammenhängender gerichteter Graph
schwach zusammenhängender gerichteter Graph
BackText: Ein Graph G heißt stark zusammenhängend, wenn alle Knoten von G voneinander erreichbar sind.
Ein Graph G heißt stark zusammenhängend, wenn alle Knoten von G voneinander erreichbar sind, aber nur bei Missachtung der Richtung der Kanten.

FrontText: starke Zusammenhangskomponenten
BackText: Die maximalen stark zusammenhängenden Teilgraphen eines gerichteten Graphen G heißen starke Zusammenhangskomponenten oder Komponenten des starken Zusammenhangs von G.

FrontText: schwache Zusammenhangskomponenten
BackText: Die maximalen zusammenhängenden Teilgraphen eines gerichteten Graphen G heißen schwache Zusammenhangskomponenten oder Komponenten des schwachen Zusammenhangs von G.

FrontText: Wald
Baum
BackText: Ein schlichter ungerichteter Graph W, der keine Kreise positiver Länge enthält, heißt Wald.
Ein Wald T, der auch zusammenhängend ist. heißt Baum.

FrontText: Euler'sche Linie
BackText: Eine Kantenfolge im Graph G heißt Euler'sche Linie, falls jeder Knoten und jede Kante in der Kantenfolge enthalten sind, und zusätzlich jede Kante genau einmal enthalten ist.

FrontText: eine geschlossene Euler'sche Linie in einem ungerichteten Graph
BackText: -Graph zusammenhängend
-∀ v ∈ V : d(v) ≡ 0 mod 2 (gerade Zahl)

FrontText: eine offene Euler'sche Linie in einem ungerichteten Graph
BackText: -Graph zusammenhängend
-∀ v ∈ V \ {AK,EK} : d(v) ≡ 0 mod 2
-AK : d(v) ≡ 1 mod 2 (ungerade Zahl)
-EK: d (v) ≡ 1 mod 2 (ungerade Zahl)

FrontText: eine offene Euler'sche Linie in einem gerichteten Graph
BackText: -Graph schwach zusammenhängend
-∀ v ∈ V \ {AK,EK} : d⁺ (v) = d⁻(v)
-AK: d⁺(v)=d⁻(v)+1
-EK: d⁺(v)=d⁻(v)−1

FrontText: eine geschlossene Euler'sche Linie in einem gerichteten Graph
BackText: -Graph schwach zusammenhängend
-∀ v ∈ V : d⁺ (v) = d⁻(v)

FrontText: Planare Graphen
BackText: Planare Graphen sind kreuzungsfrei darstellbar.

FrontText: Netzwerke
BackText: Netzwerke sind gerichtete oder ungerichtete Graphen C = (V, E), wo jeder Kante e ∈ E ein Wert w(e) ∈ R zugeordnet wird.

FrontText: Eulersche Polyederformel

FrontText: Satz von Kuratowski-Wagner
BackText: Ein Graph ist genau dann plättbar, falls er weder K5 noch K3,3
als Graphenminor enthält.

FrontText: Hamilton’sche Linie
offene HL
geschlossene HL
BackText: Eine Kantenfolge, die jeden Knoten des Graphen genau einmal beinhaltet.
offene HL: AK ≠ EK
geschlossene HL: AK = EK