Direkt zum Inhalt

Lexikon der Mathematik: zusammenhängender Graph

ein Graph, in dem für je zwei Ecken x und y ein Weg von x nach y existiert.

Zwei Ecken x und y eines Graphen G nennt man zusammenhängend, wenn es in G einen Weg von x nach y gibt. Dies definiert auf der Eckenmenge E(G) eine Äquivalenzrelation. Jeder von einer Äquivalenzklasse induzierte Teilgraph heißt Zusammenhangskomponente oder kurz Komponente von G.

Sind G1, G2,…,Gη die Komponenten von G, so ist G die Vereinigung der Graphen G1, G2,…,Gη (Vereinigung von Graphen), also \begin{eqnarray}G={G}_{1}\,\cup \,{G}_{2}\,\cup \cdots \,\cup {G}_{\eta }.\end{eqnarray} Besteht G nur aus einer einzigen Zusammenhangskomponente, so heißt der Graph zusammenhängend.

Die Anzahl der Komponenten eines Graphen G bezeichnen wir mit η(G). Die beiden Ecken u und v mögen in der gleichen Komponente eines Graphen G liegen. Ist SE(G) eine Eckenmenge, die weder u noch v enthält, so nennt man S eine u und v trennende Eckenmenge, wenn die Ecken u und v im Teilgraphen GS zu verschiedenen Komponenten gehören. In dem Fall, daß S nur aus einer Ecke besteht, spricht man auch von einer trennenden Ecke oder Artikulation.

Gleichermaßen heißt eine Kantenmenge JK(G) eine u und v trennende Kantenmenge, wenn die Ecken u und v im Faktor GJ zu verschiedenen Komponenten gehören. Enthält J nur eine Kante k, so nennt man k auch Brücke oder trennende Kante. Es ist nicht schwer zu sehen, daß eine Kante eines Graphen G genau dann eine Brücke ist, wenn sie zu keinem Kreis von G gehört.

Für eine beliebige Kante k eines Graphen G lassen sich leicht die Ungleichungen \begin{eqnarray}\eta (G)\,\le \,\eta (G-k)\,\le \,\eta (G)+1\end{eqnarray} nachweisen. Daher ist k genau dann eine Brücke im Graphen G, wenn η (Gk) = η(G) + 1 gilt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos