Mehrfachzusammenhang (k-Zusammenhang)

Ein Graph $G$ ist $k$-zusammenhängend, wenn er mehr als $k$ Knoten besitzt ($|G|>k$) und selbst nach dem Entfernen von $k-1$ beliebigen Knoten immer noch zusammenhängend bleibt ($G-X$ zusammenhängend für alle $X$ mit $|X|<k$).

Die Konnektivität $\mathcal{K}(G)$ ist das maximale $k$, für das $G$ noch $k$-zusammenhängend ist.

Links

• Schnittknoten und Brücke
• DS_vollständiger_foliensatz.pdf