C++Guns – RoboBlog blogging the bot

Shortcut links:
Basic graph definitions
Basics of shortest paths (this page)

Path lengths and distances

Sei 𝐺 = (𝑉, 𝐴) ein einfacher, gerichteter Graph und für jede Kante 𝑎 ∈ 𝐴 sei 𝑙(𝑎) eine reale Nummer und die Länge von 𝑎.

1. Die Länge von einem gewöhnlichen Path (inklusive gewöhnliche cycles) ist die Summe von den Längen von allen Kanten in diesem Path.
2. Abhängig vom Kontext, die Länge von einem generalized Path (inklusive generalized cycles) ist entweder definiert identisch zu gewöhnlichen Pathen, oder die Länge der backwards Kanten werden nicht addiert, sondern subtrahiert.
3. Wenn die Länge von einem gewöhnlichen oder generalizedn Cycle negativ ist, wird dieser Cycle einen negativen cycle genannt.
4. Für zwei Knoten 𝑠,𝑡 ∈ 𝑉, ein kürzester Path von 𝑠 nach 𝑡 ist ein (𝑠,𝑡)-path mit minimaler Länge von allen (𝑠,𝑡) Pathe.
5. Die Distance von 𝑠 nach 𝑡 ist:
   • +unendlich wenn kein (𝑠,𝑡)-path existiert;
   • -unendlich wenn es einen negativen cycle entlang (𝑠,𝑡)-path gibt;
   • Die Länge von einem kürzesten (𝑠,𝑡)-path sonst;

Note:
In diesem Kontext sind ungerichtete Graphen als symmetrische gerichtete Graphen anzusehen, so dass zwei gegensätzlich gerichtete Kanten die selbe Länge haben.
Wenn es keine negativen cycles gibt, ist die Distanz von einem Knoten zu sich selbst 0, weil der triviale Path ohne keinen die Länge 0 hat. Auf der anderen seite, wenn ein Knoten in einem negativen cycle ist, ist seine Distanz zu sich selbst -unendlich.
Weil durch den negativen cycle ja immer ein Weg mit einer noch kürzeren Länge gefunden werden kann. Und negativ ist kleiner als Null.

Subpath property of shortest paths

Statement: Für zwei Knoten 𝑠,𝑡 ∈ 𝑉, sei 𝑝 ein kürzester (𝑠,𝑡)-Path. Seit 𝑣,𝑤 ∈ 𝑉 zwei Knoten auf dem Path 𝑝, so dass 𝑣 vor 𝑤 liegt. Dann ist der subpath von 𝑝, von 𝑣 zu 𝑤 ein kürzester (𝑣,𝑤)-Path.

Beweis: Seien 𝑝₁, 𝑝₂ und 𝑝₃ die Subpathe von 𝑝 von 𝑠 nach 𝑣, von 𝑣 nach 𝑤 und von 𝑤 nach 𝑡. Für einen Widerspruchsbeweis angenommen, es gibt einen (𝑣,𝑤)-paht 𝑝₂' der kürzer ist als 𝑝₂. Dann würde die Aneinanderreihung der Pathe 𝑝₁+𝑝₂'+𝑝₃ einen kürzeren (𝑠,𝑡)-path als 𝑝 ergeben. Da 𝑝 aber schon der kürzeste (𝑠,𝑡)-path ist, ist dies ein Widerspruch.
Die Subpathe eines kürzesten Pathes sind ebenfalls kürzeste Pathe.

Anmerkung: Gewöhnlich wird nur der Fall v=s beachtet. Also dass es nur zwei Pathe gibt und die Argumentation mit dem ersten Path gemacht wird. Diese Version wird auch prefix property genannt.

Valid distance property

Definition: Für jeden Knoten 𝑢 ∈ sei 𝑑(𝑢) eine real Zahl. Irgendeinen Zahl, muss nicht die Distanz sein. Das valid distance property wird erfüllt, wenn 𝑑(𝑤) ≤ 𝑑(𝑣) + l(𝑣,𝑤) für alle Kanten (𝑣,𝑤) ∈ 𝐴.
Das ist einfach so eine Definition.

Statement: Sei 𝑠 aus 𝑉 und für jeden Knoten 𝑢 aus 𝑉 sei d(𝑢) die Distanz von 𝑠 nach 𝑢 unter Beachtung der Kantenlängen 𝑙.
Es sei d(𝑤) ≤ d(𝑣) + 𝑙(𝑣,𝑤) Für alle Kanten (𝑣,𝑤) aus 𝐴.
Das valid distance property ist erfüllt für kürzeste Wege mit Kantenlängen im Graph.

Heißt auf gut deutsch, dass es eine "kürzeste" Kante von 𝑣 nach 𝑤 gibt und alle anderen Kanten von 𝑣 nach 𝑤 sind länger. Und da 𝑣 ja beliebig sein kann, heißt es: Es gibt einen kürzesten Weg nach 𝑤 und alle andern sind länger.

Beweis: The linke Seite der Ungleichung ist die Länge von dem kürzesten (𝑠,𝑤) Path.
Die rechte Seite ist die Länge von irgendeinem (𝑠,𝑤) Path (also die Aneinanderreihnug von dem kürzesten (𝑠,𝑣) Path und einer Kante (𝑣,𝑤))

Statement distance update: In den meisten shortest-path algorithmen, für jeden Knoten 𝑣 AUS V gibt es ein Attribut d(𝑣).
Dieses Attribut entspricht die Länge von einem (s,𝑣) Path und ist die echte Distanz von s zu 𝑣 wenn der Algorithmus terminiert.
In praktisch allen standard Algorithmen, die folgende Update Operation ist die (einzige) Operation zum updaten des d-Attributs:
1. Wähle eine Kante (𝑣,w) AUS A
2. Wenn (𝑣,w) das valid distance properts verletzt, also diese Kante einen kürzeren Weg zu w ermöglicht, also d(w) > d(𝑣) + l(𝑣,w) dann setzte d(w) := d(𝑣) + l(𝑣,w)

Distances along shortest paths

Sei 𝑠 ∈ 𝑉 und für jeden Knoten 𝑢 ∈ V sei d(𝑢) die Distanz von 𝑠 nach 𝑢 unter Berücksichtigung der Kantenlängen 𝑙.

Statement: Angenommen es gibt keine negativen Cyclen. Für eine Kante (𝑣,𝑤), es ist d(𝑤) = d(𝑣) + 𝑙(𝑣,𝑤) genau dann wenn die Kante (𝑣,𝑤) die letzte Kante von einem kürzesten (𝑠,𝑤) Path ist.

Beweis:

1. Fall d(w) = d(v) + l(v,w)
   Dann hat die Aneinanderreihung von dem kürzesten Path von s nach v und (v,w) die Länge d(w) und damit die kürzeste Länge. (Weil die Kante (v,w) eben die letzte Kante im (s,w) Path ist.
2. Fall d(w) != d(v) + l(v,w)
   Wegen dem valid distanz property ist d(w) < d(v) + l(v,w) (Wenn der Path nicht über die kürzeste kante geht, dann über eine Längere, also ist die Distanz auch größer als die kürzeste Distanz d(w)). Für einen Widerspruchsbeweis angenommen, dass ein kürzester (s,w) Path ist von der Form p + (v,w). Dann hat p die Länge d(w) - l(v,w) < d(v) was ein Widerspruch zur Definition von d(v) ist.

Reconstruction of a shortest path from the distances

Angenommen, dass für die Knoten 𝑠,𝑡 ∈ V die Distanz d_𝑠(t) von 𝑠 to 𝑡 unter Beachtung der Kantenlängen l, welche eine reale Nummer ist (weder +inf noch -inf). Dann kann ein kürzester (𝑠,𝑡) Path 𝑝 wie folgt konstruiert werden.

1. Initialisiere 𝑝 als leer
2. Setzte 𝑤 := 𝑡 - Wir konstruieren den Path rückwärts von 𝑡 nach 𝑠
3. While w /= s
   1. Finde eine Kante (𝑣,𝑤), so dass d_𝑠(𝑤) = d_𝑠(𝑣) + l(𝑣,𝑤)
   2. Füge die Kante (𝑣,𝑤) an den Anfang von 𝑝 an
   3. Setze 𝑤 := 𝑣

Constructing a shortest-paths arborescence or a negative cycle

Wie beim Valid distance property erwähnt, benutzen die meisten Algorithmen für das kürzeste Wege Probleme eine Standard Update Operation. Diese Operation kann wie folgt erweitert werden (mit 𝑠 für den Startknoten).
Jeder Knoten v ∈ V speichert eine von den incoming Kanten als zusätzliches Attribut:

1. Initialisierung des Attributs:
   Dieses Attribut wird für den Knoten s mit void initialisiert.
   Für alle anderen Knoten v, die mit d(v) = +inf initialisiert wurden, wird dieses Attribut auch mit void initialisiert.

   Je nachdem ob die ausgehenden Kanten von s bei der Initialisierung beachtet, oder erst während der Iteration, ist die Distanz der abgehenden Knoten von s damit nicht +inf.
   Und das zusätzliche Attribut dieser Knoten wird mit der initial incoming Kante (s,v) initialisiert.

2. Update: Wann immer die Standard Update Operation auf eine Kante (v,w) angewendet wird (also das Aktualisieren von der Distanz), wird diese Kante (v,w) die incoming Kante von W. Also speichert das zusätzliche Attribut immer die zuletzt gesehene Kante.

Statement:
Betrachte ein Algorithmus welcher ein kürzesten (s,v) Path für jeden Knoten v ∈ V liefert, dabei sind die die Distanzen von s eine real Nummer (weder -inf noch +inf).

Bei Terminierung gelten folgende Statements:

1. Die incoming Kante von s ist void genau dann wenn s nicht auf einem negative cycle Paht liegt. (Das ist auch so, selbst wenn s auf einem positive cycle Path liegt. Weil der kürzeste Weg von s nach t geht nicht nochmal über s.)
2. Die gespeicherten Kanten in dem zusätzlichen Attribut bilden ein cycle genau dann wenn die erreichten Knoten einen negativen Cycle bilden. (Einen positiven cycle bilden die Knoten ja nicht, das wissen wir bereits.)
   Jeder cycle in diesen ausgewählten Kanten ist ein negative cycle. (Weil es positive Cycle ja nicht gibt)
3. Wenn die erreichten Knoten von s aus keinen negativen cycle enthält (Und positive cycle haben wir ja nicht), dann bilden die gewählten Kanten eine arborescene bei der der Knoten s die Wurzel ist und die arborescene spannt über alle erreichten Knoten.
   Für jeden erreichbaren Knoten v ∈ V, der Path von s zu v in dieser Arborescene ist ein kürzester (s,v)-Path. (Ja was sonst wenn man einen shortest-path Algo laufen lässt.)

(Was ist das Problem mit negativne cycle bei andern Algos? Die Terminieren nicht?)

Beweis:
Der Algorithmus liefert d(s) < 0 genau dann wenn s auf einem negativen cycle ist. (Positive cycle gibts ja nicht und sonst ist d(s) > 0). Genau in diesem Fall wird die incoming Kante von s geupdated.
Das Beweis Statement Satz 1. (Zur Erinnerung: Satz 1: Die incoming Kante von s ist void wenn NICHT negative cycle. Wenn nicht dann void.)

(Aber woher wissen wir, dass der Algo das denn auch wirklich tut?)

Für den 2. Satz beachte erst, dass der zweite Satz impliziert den only-if Teil von dem ersten Satz, so müssen wir nicht den only-if Teil von dem ersten Satz beachten.
Sei v ein erreichbarer Knoten auf einen negative cycle. Sei p ein Path auf ausgewählten Kanten welcher in v endet.
Im Besonderen, lass p eine maximale anzahl voN Kanten von allen möglichen dieser Pathe.
Dann p kann nicht an s starte, weil der algorithmus wird eine distanz Wert für v liefern, welcher kleiner ist als die echte Distanz.
Klar, p cann nicht an einem unreachable Knoten starten. Super Klar.

(Admissible/zulässige) node potentials

Für jeden Knoten 𝑣 ∈ 𝑉, sei h(𝑣) eine reale Nummer.
Für Kante 𝑎 = (𝑣,𝑤) ∈ 𝐴, sei 𝑙^h(𝑎) := 𝑙(𝑎) - h(𝑣) + h(𝑤)
In diesem Kontext, diese Werte werden gewöhnliche node potential genannt.
Node potentials sind zulässig wenn 𝑙(𝑎) >= 0 für alle 𝑎 ∈ 𝐴. Also Kantengewicht(länge) positiv ist.

Statement:
Ein (𝑠,𝑡)-path ist kürzer als ein anderer (𝑠,𝑡)-path unter der Berücksichtigung der Kantenlängen 𝑙^h, genau dann wenn die selbe Aussage auch wahr ist für die Kantenlängen 𝑙. Also die shortest path Algorithmen funktionieren auch weiterhin.
Im Besonderen, der kürzeste Path unter Berücksichtigung der Kantenlängen 𝑙^h ist exakt der selbe kürzeste Path unter Beachtung der Kantenlängen 𝑙. Also die Algorithmen geben sogar das selbe Ergebnis zurück. Wir haben nichts kaputt gemacht. Nur verbesser.

Beweis:
Set 𝑠 = 𝑣₁ - 𝑣₂ - ... - 𝑣_k = 𝑡 die Knoten auf einem (𝑠,𝑡)-path. Gemein ist dass s = 𝑣₁ und t = 𝑣_k
Die Länge auf diesem Path unter Berücksichtigung von 𝑙^h ist dann *einsetzen und umformen von 𝑙^h und 𝑙 *
Also: Die Länge von einem (𝑠,𝑡)-path unter Berücksichtigung von 𝑙^h und 𝑙, unterscheidet sich nur durch eine Konstante h(𝑡) - h(𝑠).

Ist ja auch klar: Wenn für jede Kante h(𝑣) subtrahiert und h(𝑤) addiert wird, und bei der nächsten Kante im Path w mit dem nächsten v tauscht. Dann heben sich die Termen in dieser Summe bis auf den ersten und letzten auf.

Anmerkung:
Admissible/zulässige node potential ermöglichen effiziente Algorithmen wie Dijkstra, welche nicht-negative Kanten Längen erwarten. Durch die node potentials kann man negative Kanten Längen ins positive ziehen.

G
𝐺
V
𝑉
A
𝐴
E
𝐸
K
𝐾
a
𝑎
k
𝑘
l
𝑙
m
𝑚
n
𝑛
p
𝑝
s
𝑠
t
𝑡
u
𝑢
v
𝑣
w
𝑤
Teilemenge
⊆
phi
φ
Element von
∈

Shortcut links:
Basic graph definitions (this page)
Basics of shortest paths

Gerichtete und ungerichtete Graphen

1. Ein gerichteter Graph 𝐺 = (𝑉, 𝐴) besteht aus einer endlichen Menge 𝑉 von Knoten und einem multiset 𝐴 von geordneten Paaren von Knoten. Die Elemente von 𝐴 sind die gerichteten Kanten von 𝐺.
2. Ein ungerichteter Graph 𝐺 = (𝑉, 𝐸) besteht aus einer endlichen Menge 𝑉 von Knoten und ein multiset 𝐸 von ungeordneten Paaren von Knoten. Die Elemente von 𝐸 sind die ungerichteten Kanten von 𝐺.
3. Ein gerichteter oder ungerichteter Graph ist simple (einfach), wenn:
   • Kein Knoten, in 𝐴 oder 𝐸, mit sich selbst verbunden ist
   • Die multisets 𝐴 oder 𝐸 sind nur sets
4. Ein gerichteter Graph 𝐺 = (𝑉, 𝐴) ist
   • symmetrisch, wenn (𝑣,𝑤) ∈ 𝐴 impliziert (𝑤,𝑣) ∈ 𝐴
   • anti-symmetrisch, wenn (𝑣,𝑤) ∈ 𝐴 impliziert (𝑤,𝑣) ∉ 𝐴

Adjacency, incidence, degree (benachbart, verbunden, Grad)

1. Zwei Knoten eines gerichteten oder ungerichteten Graphen heißen adjacent (benachbart), wenn sie mindestens eine gemeinsame Kante haben.
2. Ein Knoten und eine Kante heißen incident (verbunden), wenn der Knoten zu der Kante gehört.
3. Zwei Kanten heißen incident (verbunden), wenn sie mindestens einen gemeinsamen Knoten haben.
4. Für einen Knoten, die Anzahl der incident (verbundenen) Kanten ist der Grad von diesem Knoten. Ein Knoten mit Grad 0 heißt isoloert.
5. Betrachte einen gerichteten Graph 𝐺 = (𝑉, 𝐴):
   1. Für eine Kante 𝑎 = (𝑣,𝑤) ∈ 𝐴, 𝑣 ist der tail (Fuß,Startknoten) von 𝑎 und 𝑤 ist der head (Kopf/Endknoten) von 𝑎.
   2. Eine Kante 𝑎 = (𝑣,𝑤) ∈ 𝐴 ist eine outgoing (abgehende) Kante von 𝑣 und eine incoming (eingehende) Kante von 𝑤.
   3. outdegree von einem Knoten 𝑣 ∈ 𝑉 ist die Anzahl der abgehenden Kanten.
   4. indegree von einem Knoten 𝑣 ∈ 𝑉 ist die Anzahl der eingehenden Kanten.

Transpose of a graph

Für einen gerichteten Graph 𝐺 = (𝑉, 𝐴), die transpose (Vertauschung) von 𝐺 ist das Ergebnis vom Drehen aller Kanten von 𝐺. (Start- und Zielknoten tauschen)

Subgraph

1. Gegeben sind zwei einfache, ungerichtete Graphen 𝐺₁ = (𝑉1, 𝐸1) und 𝐺2 = (𝑉2, 𝐸2).
   Dann ist 𝐺1 ein subgraph von 𝐺2, wenn es eine Knotenteilmenge 𝑉' ⊆ 𝑉2 gibt und eine bijektive (umkehrbare) Funktion φ: 𝑉1 -> 𝑉' gibt, welche alle Knoten aus 𝑉1 auf die Teilmenge 𝑉' von 𝑉2 abbildet, und zwar genau so, dass eine Kante {𝑣,𝑤} aus 𝐸1 impliziert, dass es eine andere Kante {φ(𝑣),φ(𝑤)} ∈ 𝐸2 gibt.
   Denn es müssen nicht nur alle Knoten von 𝑉1 in 𝑉2 zu finden sein, sondern natürlich auch alle Kanten.
2. Gegeben sind zwei einfache, gerichtete Graphen 𝐺₁ = (𝑉1, 𝐴1) und 𝐺2 = (𝑉2, 𝐴2).
   Dann ist 𝐺1 ein subgraph von 𝐺2, wenn es eine Knotenteilmenge 𝑉' ⊆ 𝑉2 gibt und eine bijektive (umkehrbare) Funktion φ: 𝑉1 -> 𝑉' gibt, welche alle Knoten aus 𝑉1 auf die Teilmenge 𝑉' von 𝑉2 abbildet, und zwar genau so, dass eine Kante (𝑣,𝑤) aus 𝐴1 impliziert, dass es eine andere Kante (φ(𝑣),φ(𝑤)) ∈ 𝐴2 gibt.
   Quasi das selbst wie für ungerichtete Grapen.
3. Ein spanning subgraph von einem ungerichteten oder gerichteten Graphen 𝐺 ist ein subgraph welcher alle Knoten von 𝐺 enthält.
   Aber nicht alle Kanten (es bildet sich ein Baum).

Paths

1. Ein ordinary (gewönlicher) Path in einem ungerichteten Graphen ist eine endliche, geordnete Sequenz ({v₁,v₂}, {v₂,v₃}, ..., {v_k-2, v_k-1}, {v_k-1,v_k}) von Kanten.
2. Ein ordinary (gewöhnlicher) Path in einem gerichteten Graphen ist eine endliche, geordnete Sequenz ((v₁,v₂), (v₂,v₃), ..., (v_k-2, v_k-1), (v_k-1,v_k)) von Kanten.
3. Ein generalized a.k.a. weak (genereller, schwacher) Path in einem gerichteten Graphen ist eine endliche Sequenz ((v₁,w₁), (v₂,w₂), ..., (v_k-1, w_k-1), (v_k,w_k)), so dass drehen von einigen Kanten einen ordinary Path ergibt (Ein ordinary Path ist schon ein generalized Path bei dem keine Kanten gedreht werden müssen).
4. Ein Path ist simple (einfach) wenn er keine Knoten doppelt enthält.
5. Ein Knoten 𝑡 ∈ 𝑉 ist reachable (erreichbar) von 𝑠 ∈ 𝑉, wenn es einen Path von 𝑠 nach 𝑡 in dem Graph gibt.
   Abhängig vom Kontext, der Path muss ein ungerichteter, ein gewöhnlicher gerichteter, oder ein generalized Path sein.
   Jeder Knoten ist von sich selbst aus erreichbar, via den trivialen Path welcher nur diesen Knoten enthält und sonst keine Kanten.
6. Die internal (internen) Knoten von einem Path jeglicher Art sind alle Knoten von diesem Path außer dem Start und Endknoten.
   (Wenn der Start oder Endknoten mehr als einmal im Path vorkommt, zählt es zu den internen Knoten)
7. Zwei Pathe sind edge-disjoint (disjunkt) wenn sie keine gemeinsame Kante haben. Sie sind (internally) node-disjoint wenn sie keine gemeinsamen Knoten haben.

Cycles

1. Ein (ordinaty/gewöhnlicher) cycle in einem ungerichteten Graphen ist eine endliche, geordnete Sequenz ({v₁,v₂}, {v₂,v₃}, ..., {v_k-2, v_k-1}, {v_k-1, v₁} ) von Kanten. In anderen Worten: Ein cycle ist ein Path, so dass der Startknoten gleich dem Endknoten ist.
2. Ein (ordinaty/gewöhnlicher) cycle in einem gerichteten Graphen ist eine endliche, geordnete Sequenz ((v₁,v₂), (v₂,v₃), ..., (v_k-2, v_k-1), (v_k-1, v₁) ) von Kanten. In anderen Worten: Ein cycle ist ein Path, so dass der Startknoten gleich dem Endknoten ist.
3. Ein generalized a.k.a. weak (genereller, schwacher) cycle in einem gerichteten Graphen ist eine endliche Sequenz ((v₁,w₁), (v₂,w₂), ..., (v_k-1, w_k-1), (v_k,w_k)), so dass drehen von einigen Kanten einen ordinary cycle ergibt (Ein ordinary cycle ist schon ein generalized cycle bei dem keine Kanten gedreht werden müssen).
4. A cycle is simple if no proper part is a cycle of its own.
5. Ein gerichteter oder ungerichteter Graph ist acyclic (cycle-free), wenn er kein ordinary cycle enthält. Ein gerichteten Graphen nennt man in diesem Fall DAG (directed acyclic graph).
6. Für zwei Knoten 𝑠,𝑡 ∈ 𝑉, ein (s,t)-graph 𝐺 = (𝑉, 𝐴) ist ein DAG, so dass 𝑠 ist der einzige Knoten mit indegree 0, und 𝑡 ist der einzige Knoten mit outdegree 0.
   Ein DAG ist ein (s,t)-Graph , genau dann, wenn der Graph G die Vereinigung von (nicht notwenigerweise internally Knoten oder Kanten disjunkt) allen (s,t)-pathen ist.

Forests, trees, branchings, arborescences

1. Ein forst ist ein cycle-free undirected Graph. Disconnected nicht vergessen sonst macht es kein Sinn.
   
2. Ein tree ist ein conected forst. Also connected, cycle-free undirected Graph.
   
   Das ist nicht unbedingt das, was man von der Schule her noch kennt. In der Schule war ein tree immer ein directer Graph mit einem Wurzelknoten. Aber gut. Muss ja nicht.
3. Ein branching ist ein cycle-free, directed Graph, so dass indregree für jeden Knoten 0 oder 1 ist. Das sieht gedanklich schon ehr wie ein Baum aus. Aber noch nicht ganz. Directed muss sein, klar. Sonst könnte man seine "Entscheidungen" beim "branchen" ja zurück nehmen.
4. Eine arborescene ist ein branching, so dass genau ein Knoten indegree 0 hat. Das nennt man auch rooted trees und der einzigartige Knoten mit indegree 0 ist root. DAS ist ein Baum.
5. Ein forest/tree/branching/arborescence in einem Graphen G ist ein Subgraph von G welcher wiederrum ein forest/tree/branching/arborescence ist.
   Naja, auf dem zweiten Blick stimmt das. Jeden Subgraph den man aus einem Tree rausholt ist wieder ein Tree.

Connectedness

Types of connectedness:

Types of connectedness:
1. Ein ungerichteter Graph ist connected, wenn jedes mögliche Knotenpaar durch einen Path verbunden ist.
2. Ein ungerichteter Graph ist k-connected, wenn jedes mögliche Knotenpaar mindestens durch k internally node-disjoint Pathe verbunden ist. Einfach nur connected ist 1-connected. k=2 ist biconnected.
3. Ein directed Graph ist weakly connected, wenn für jeden Knotenpaar ein generalized path existiert welcher diese Knoten verbindet.
4. Ein directed Graph ist strongly connected, wenn für jedes geordnerte Knotenpaar ein ordinary path den ersten mit den zweiten Knoten verbindet.

Links:

5. Ein articulation Knoten in einem connected undirected Graph ist so ein Knoten, dass wenn der Knoten (und die angeschlossenen Kanten) entfernt wird, der Graph disconnected wird.
6. Eine bridge in einem connected undirected Graph ist eine Kante, so dass der Graph disconnected wird wenn diese Kante entfernt wird.

Connected components:

7. Die k-connected componenten von einem ungerichteten Graphen 𝐺 = (𝑉, 𝐸) ist die inclusion-maximal Knotenmengen 𝑉' ⊆ 𝑉, so dass der Subgraph von 𝐺, hergestellt von 𝑉', k-connected ist (d.h. wenn jedes mögliche Knotenpaar in V' mindestens durch k internally node-disjoint paths miteinander verbunden sind).
   For k=1 wir sagen connected und für k=2 wir sachen biconnected compoenten von G.
8. Die weakly und strongly connecten componenten von einem directed Graph 𝐺 = (𝑉, 𝐴) sind die inclusion-maximal Knotenmengen 𝑉' ⊆ 𝑉, so dass der Subgraph von 𝐺 induced von 𝑉' ist weak und strong connected.

Bipartite and k-partite graphs

Sei 𝐺 = (𝑉, 𝐸) ein ungerichteter Graph.

1. Der Graph 𝐺 ist 𝑘-partite, wenn es eine 𝑘-partition {𝑉₁, ..., 𝑉_k} von 𝑉 gibt, so dass {𝑣,𝑤} ∉ 𝐸 ist für jedes Paar 𝑣,𝑤 ∈ 𝑉_i für jedes i ∈ {1,...,𝑘}.
2. Für 𝑘=2 wir sagen 𝐺 ist bipartite.

Statement: Ein verbundener, ungerichteter Graph ist bipartite, genau dann wenn es kein Cycle von ungerade Länge gibt.
Das lässt sich leicht erkennen, wenn man die Knoten auf dem Path abwechseln V1 und dann V2 zuordnet. Bei ungeraden Längen sind die Knoten der letzten Kante bei immer aus V1 oder V2.

Complete graphs

1. Für eine positive ganzzahlige Nummer 𝑛, der complet graph 𝐾_𝑛 = (𝑉,𝐸) ist der einzigartige undirecte Graph, so dass |𝑉| = 𝑛 und alle (ungeordneten) Paaren of Knoten in 𝐸 sind. Das heisst jeder mit jedem. Dense.
2. Für positive ganzzahlige Nummern 𝑚 und 𝑛, der complete bipartite graph 𝐾_𝑚,𝑛 = (𝑉₁ UNITED 𝑉₂, 𝐸) ist der einzigartige undirecte graph, so dass |𝑉₁| = 𝑚 und |𝑉₂| = 𝑛 und jeder (ungeordnete) Pair {𝑣,𝑤} mit 𝑣 ∈ 𝑉₁ und 𝑤 ∈ 𝑉₂ in 𝐸 ist.
   Also jeder von dem einem mit jeder von dem anderen.