maximale Zusammenhangskomponente

12.12.2005, 19:58	TheMan	Auf diesen Beitrag antworten »
maximale Zusammenhangskomponente Hi, ich hab folgende Aufgabe als Übung auf und versteh dabei den Begriff (maximale) Zusammenhangskomponente nicht: Ein ungerichteter Graph $\begin{eqnarray} G=(V,E) \end{eqnarray}$ heißt zusammenhängend, wenn für jedes Paar von Knoten $\begin{eqnarray} u,v \in V \end{eqnarray}$ ein Pfad von $\begin{eqnarray} u \end{eqnarray}$ nach $\begin{eqnarray} v \end{eqnarray}$ in $\begin{eqnarray} G \end{eqnarray}$ existiert. Ist $\begin{eqnarray} G \end{eqnarray}$ nicht zusammenhängend, so zerfällt $\begin{eqnarray} G \end{eqnarray}$ in (maximale) Zusammenhangskomponenten, d.h. $\begin{eqnarray} V = \bigcup^{k}_{i=1}V_{i} \end{eqnarray}$ (die $\begin{eqnarray} V_i \end{eqnarray}$ paarweise disjunkt) und $\begin{eqnarray} G \end{eqnarray}$ jeweils eingeschränkt auf $\begin{eqnarray} V_i \end{eqnarray}$ ist zusammenhängend. Zeigen sie, dass die Anzahl (maximaler) Zusammenhangskomponenten in einem Graphen mindestens $\begin{eqnarray} \|V\| - \|E\| \end{eqnarray}$ ist. Wie muss ich den Begriff (maximale) Zusammenhangskomponenten verstehen ? Wenn ich annehme, dass maximal bedeutet, dass die Zusammenhangskomponenten intern vollständig verbunden sind, dann stimmt die Behauptung nicht, da dann mehr Kanten als Knoten existieren und die Anzahl der Zusammenhangskomponenten negativ wäre. Für den Beweis ist es eigentlich nur sinnvoll, wenn die Zusammenhangskomponenten minimal verbunden wären, also Kantenanzahl um 1 kleiner ist als Knotenanzahl. (dann ist aber das maximal irgendwie irreführend) Vielen Dank schon mal für eure Antworten... Gruß TheMan
12.12.2005, 22:25	Mazze	Auf diesen Beitrag antworten »
Den Begriff einer maximalen Zusammenhangskomponente kenn ich auch nicht. Aber die Definition davon sieht exakt so aus wie die der Zusammenhangskomponente. Ergibt für mich auch irgendwie keinen Sinn, für jeden Knoten einer Komponente der eine Verbindung zu einem anderen hat ist die Kante sowieso in der Komponente. Da von maximal zu reden macht für mich keinen Sinn. Aber ich wäre da vorsichtig, nur weil ichs nicht kenne heißt es nicht das es das nicht gibt. Ich würd direkt mal nen Tutor oder so fragen was das zu bedeuten hat. Beim googlen hab ich auf die schnelle auch nichts gefunden.
13.12.2005, 19:25	irre.flexiv	Auf diesen Beitrag antworten »
Also Zusammenhangskomponenten sind beliebige zusammenhängende Teilgraphen, die müssen also nicht maximal sein. Maximal ist sie genau dann wenn für alle Kanten von G gilt das Anfangs- und Endknoten entweder beide in der Zusammenhangskomponente liegen oder gar nicht. Das die Differenz negativ wird muss dich nicht stören. In diesem Fall ist die Anzahl mindestens 1 falls \|V\|>0, und 0 falls \|V\|=0. Das hätte der Aufgabensteller vielleicht noch erwähnen sollen Edit: Die Def. von maximal hat nicht hingehauen. Das hab ich mal geändert.
13.12.2005, 20:23	TheMan	Auf diesen Beitrag antworten »
danke für die Antwort... ich glaub jetzt müsst ichs hinkriegen

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »