Eine zusammenhängende Komponente ist ein maximal zusammenhängender Teilgraph eines ungerichteten Graphen. Jeder Knoten gehört zu genau einer zusammenhängenden Komponente, ebenso wie jede Kante. Ein Graph ist dann und nur dann zusammenhängend, wenn er genau eine zusammenhängende Komponente hat.
Die starken Komponenten sind die maximal stark zusammenhängenden Teilgraphen eines gerichteten Graphen.
Ein Scheitelpunktsschnitt oder eine Trennmenge eines zusammenhängenden Graphen G ist eine Menge von Scheitelpunkten, deren Entfernung dazu führt, dass G nicht mehr verbunden ist. Die Vertex-Konnektivität κ(G) (wenn G kein vollständiger Graph ist) ist die Größe eines minimalen Vertex-Schnitts. Ein Graph heißt k-vertex-connected oder k-connected, wenn seine Vertex-Connectivity k oder größer ist.
Genauer gesagt, jeder Graph G (vollständig oder nicht) heißt k-vertex-connected, wenn er mindestens k+1 Scheitelpunkte enthält, aber keine Menge von k – 1 Scheitelpunkten, deren Entfernung den Graphen trennt; und κ(G) ist definiert als das größte k, so dass G k-connected ist. Insbesondere hat ein vollständiger Graph mit n Scheitelpunkten, bezeichnet mit Kn, überhaupt keine Scheitelpunktschnitte, sondern κ(Kn) = n – 1.
Ein Scheitelpunktsschnitt für zwei Scheitelpunkte u und v ist eine Menge von Scheitelpunkten, deren Entfernung aus dem Graphen u und v voneinander trennt. Die lokale Konnektivität κ(u, v) ist die Größe des kleinsten Scheitelpunktsschnitts, der u und v trennt. Die lokale Konnektivität ist symmetrisch für ungerichtete Graphen, d. h. κ(u, v) = κ(v, u). Außerdem ist, außer bei vollständigen Graphen, κ(G) gleich dem Minimum von κ(u, v) über alle nicht benachbarten Paare von Knoten u, v.
2-Konnektivität wird auch Bikonnektivität genannt und 3-Konnektivität wird auch Trikonnektivität genannt. Ein Graph G, der zusammenhängend, aber nicht 2-zusammenhängend ist, wird manchmal als trennbar bezeichnet.
Analoge Konzepte können für Kanten definiert werden. Im einfachen Fall, in dem das Schneiden einer einzelnen, spezifischen Kante den Graphen trennen würde, nennt man diese Kante eine Brücke. Allgemeiner ausgedrückt, ist ein Kantenschnitt von G eine Menge von Kanten, deren Entfernung dazu führt, dass der Graph nicht mehr verbunden ist. Die Kantenkonnektivität λ(G) ist die Größe eines kleinsten Kantenschnitts, und die lokale Kantenkonnektivität λ(u, v) von zwei Knoten u, v ist die Größe eines kleinsten Kantenschnitts, der u von v trennt. Ein Graph heißt k-Kanten-verbunden, wenn seine Kantenkonnektivität k oder größer ist.
Ein Graph heißt maximal verbunden, wenn seine Konnektivität gleich seinem minimalen Grad ist. Ein Graph heißt maximal kantenverbunden, wenn seine Kantenkonnektivität gleich seinem minimalen Grad ist.
Super- und Hyper-KonnektivitätBearbeiten
Ein Graph heißt super-verbunden oder super-κ, wenn jeder minimale Scheitelschnitt einen Scheitelpunkt isoliert. Ein Graph wird als hyper-connected oder hyper-κ bezeichnet, wenn die Löschung jedes minimalen Vertex-Cuts genau zwei Komponenten erzeugt, von denen eine ein isolierter Vertex ist. Ein Graph ist semi-hyper-connected oder semi-hyper-κ, wenn jeder Minimum-Vertex-Cut den Graphen in genau zwei Komponenten aufteilt.
Genauer gesagt: Ein G-verbundener Graph ist super-connected oder super-κ, wenn alle Minimum-Vertex-Cuts aus den Scheitelpunkten bestehen, die an einen (minimum-degree) Scheitelpunkt angrenzen.Ein zusammenhängender Graph G heißt super-edge-connected oder super-λ, wenn alle minimalen edge-cuts aus den Kanten bestehen, die zu einem (minimum-degree) vertex gehören.
Eine Schnittmenge X von G heißt eine nicht-triviale Schnittmenge, wenn X nicht die Nachbarschaft N(u) eines beliebigen vertex u ∉ X enthält. Dann ist die Superconnectivity κ1 von G:
κ1(G) = min{|X| : X ist eine nicht-triviale Schnittmenge}.
Ein nichttrivialer Kantenschnitt und die Kanten-Superkonnektivität λ1(G) sind analog definiert.
