0 Daumen
1,9k Aufrufe

Aufgabe:

Ich betrachte einen ungerichteten Graphen G=(V,E) mit Knotenmenge V und Kantenmenge E. G wird zusammenhängend genannt, wenn für alle Knoten v,w∈V(G) ein v-w-Weg existiert.

Nun zum Begriff der Zusammenhangskomponente. Wie ist hier das Wort ,,maximal'' zu verstehen?

Avatar von 15 k

1 Antwort

+1 Daumen

Der Begriff "Maximal zusammenhängender Teilgraph \(U\) von \(G\)" bedeutet:

1. Der Teilgraph \(U\) ist zusammenhängend

2. Für jeden Knoten \(v\in G\setminus U\) ist der Teilgraph \(U\cup\{v\}\) nicht zusammenhängend


In deutsch: Maximal bedeutet, dass du keinen weiteren Knoten hinzufügen kannst, ohne Zusammenhang zu zerstören.

Intuitiv kannst du dir Zusammenhang so vorstellen: Ein ungerichteter Graph ist aufteilbar in zusammenhängende "Inseln", zwischen denen es keine Kante gibt. Dieser Fakt ist äquivalent zu der Aussage, dass die Relation \((x\cong y \iff \text{Es existiert ein x-y-Weg})\) eine Äquivalenzrelation ist. Diese Inseln sind die Zusammenhangskomponenten, quasi die Äquivalenzklassen des Quotienten \(G/\cong\).

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community