Wir haben Beispiele für zusammenhängende Graphen und Graphen, die nicht zusammenhängen, gesehen. Während „nicht zusammenhängend“ so gut wie eine Sackgasse ist, kann man viel darüber sagen, „wie zusammenhängend“ ein zusammenhängender Graph ist.Die einfachste Herangehensweise ist, zu untersuchen, wie schwer es ist, einen Graphen durch Entfernen von Knoten oder Kanten zu trennen. Wir nehmen an, dass alle Graphen einfach sind.
Wenn es möglich ist, einen Graphen durch das Entfernen eines einzelnen Scheitelpunktes, eines so genannten Cutpoints, zu trennen, sagen wir, der Graph hat Konnektivität1. Wenn dies nicht möglich ist, es aber möglich ist, den Graphen durch das Entfernen von zwei Scheitelpunkten zu trennen, hat der Graph Konnektivität 2.
Dasselbe tun wir für Kanten:
Theorem 5.7.3 $\kappa(G)\le\lambda(G)$.
Graphen, die 2-Verbindungen haben, sind besonders wichtig, und das folgende einfache Theorem ist nützlich.
Es gibt weitere schöne Charakterisierungen von 2-verbundenen Graphen.
Das folgende Korollarium ist eine einfache Umformulierung dieses Theorems.
Diese Version des Theorems legt eine Verallgemeinerung nahe:
Wir beweisen zunächst die ursprüngliche Version von Menger, eine „lokale“ Version.
Theorem 5.7.9 Wenn $v$ und $w$ nicht benachbarte Scheitelpunkte in $G$ sind, ist $\kappa_G(v,w)=p_G(v,w)$.
Wir kehren kurz zur 2-Konnektivität zurück.Der nächste Satz kann manchmal verwendet werden, um den Induktionsschritt in einem Induktionsbeweis zu liefern.
Ein Graph, der nicht verbunden ist, besteht aus verbundenen Komponenten. In einem ähnlichen Theorem sehen wir, dass zusammenhängende Graphen, die nicht2-zusammenhängend sind, aus 2-zusammenhängenden Teilgraphen und Brücken konstruiert werden.
Definition 5.7.11 Ein Block in einem Graphen $G$ ist ein maximalinduzierter Teilgraph auf mindestens zwei Scheitelpunkten ohne Schnittpunkt.
Maximal bedeutet hier wie üblich, dass der induzierte Untergraph $B$ nicht durch Hinzufügen von Knoten oder Kanten vergrößert werden kann (unter Beibehaltung der gewünschten Eigenschaft, in diesem Fall, keine Schnittpunkte).Ein Block ist entweder ein induzierter Untergraph mit zwei Verbindungen oder eine einzelne Kante mit ihren Endpunkten. Blöcke sind vor allem wegen dieses Theorems nützlich:
Theorem 5.7.12 Die Blöcke von $G$ partitionieren die Kanten.
Wenn $G$ einen einzelnen Block hat, ist er entweder $K_2$ oder 2-verbunden, und jeder 2-verbundene Graph hat einen einzelnen Block.
Theorem 5.7.13 Wenn $G$ zusammenhängend, aber nicht 2-zusammenhängend ist, dann ist jeder Knoten, der in zwei Blöcken liegt, ein Schnittpunkt von $G$.
Übungen 5.7
Ex 5.7.1Angenommen, ein einfacher Graph $G$ mit $n\ge 2$ Scheitelpunkten hat mindestens$\ds {(n-1)(n-2)\über2}+1$ Kanten. Beweisen Sie, dass $G$ zusammenhängend ist.
Ex 5.7.3Angenommen, $G$ ist einfach mit der Gradfolge $d_1\le d_2\le\cdots\le d_n$, und für $k\le n-d_n-1$, $d_k\ge k$. Zeigen Sie, dass $G$ zusammenhängend ist.
Ex 5.7.4Erinnern Sie sich, dass ein Graph $k$-regulär ist, wenn alle Scheitelpunkte den Grad $k$ haben. Was ist die kleinste ganze Zahl $k$, die dies wahr macht:
Wenn $G$ einfach ist, $n$ Scheitelpunkte hat, $m$ge k$, und $G$ $m$-regulär ist, dann ist $G$ zusammenhängend.
(Natürlich hängt $k$ von $n$ ab.)
Ex 5.7.6Finde einen einfachen Graphen mit $\kappa(G)
Beachte, dass ein Schnittpunkt in mindestens zwei Blöcken enthalten ist, so dass alle abhängigen Knoten des Block-Schnittpunkt-Graphen Blöcke sind. Diese Blöcke werden Endblöcke genannt.
Ex 5.7.10Zeichnen Sie den Block-Schnittpunkt-Graphen des folgenden Graphen.