[Graphentheorie] Bipartition => zusammenhängender Graph

30.01.2017, 10:15	diego09	Auf diesen Beitrag antworten »
[Graphentheorie] Bipartition => zusammenhängender Graph Moin Zusammen, habe zu erst mal eine Verständnisfrage zu einer Aufgabe aus der Graphentheorie. Aufgabenstellung: Zeigen Sie: Ein Graph G = (V, E) ist genau dann zusammenhängend, wenn zu jeder Bipartition {V1,V2} von V mit $\begin{eqnarray} V1\neq \emptyset,V2\neq \emptyset \end{eqnarray}$ eine Kante $\begin{eqnarray} {v1,v2} \in E \end{eqnarray}$ existiert, mit $\begin{eqnarray} v1 \in V2,v2 \in V1 \end{eqnarray}$ . Mir geht es hier um den Begriff "Bipartition". Laut meiner Definition und auch denen, die ich bei Google gefunden habe, werden bei einem bipartiten Graph G=(V,E) mit V={V1,V2}, die Teilmengen V1,V2 jeweils Bipartition genannt. Wenn diese Definition so korrekt ist, dann ist die Aussage dieser Aufgabenstellung doch falsch. Siehe Skizze im angehängten Screenshot. Der Graph ist offensichtlich nicht zusammenhängend, es existieren aber zu jeder Bipartition Kanten zur entsprechend anderen. Wo ist hier mein Denkfehler? Danke und Gruß Eldiego
30.01.2017, 11:24	Elvis	Auf diesen Beitrag antworten »
Das ist nur eine Bipartition, eine andere enthält z.B. die beiden linken Knoten (U1) und die 4 rechten Knoten (U2). Es gibt keine Kante von U1 nach U2, der Graph ist nicht zusammenhängend.
30.01.2017, 11:39	diego09	Auf diesen Beitrag antworten »
Danke dir schon mal für deine Antwort. Also verstehe ich den Begriff Bipartition anscheinend falsch. Ich dachte bis jetzt die Teilmenge V1 wird Bipartition von V genannt, ebenso wie V2 Bipartition von V ist. Ich bin mir nicht sicher, ob ich es jetzt richtig verstanden habe, aber nach deinem Post denke ich, dass es folgendermaßen ist: Als Bipartition wird die Verbindung der Teilmengen V1 und V2 bezeichnet. Also ist meine Ursprungsskizze eine Bipartition und die linke angehängte Skizze wäre eine weitere Bipartition. Wenn ich jetzt also alle Bipartitionen einzeichne, würde es der rechten angehängten Skizze entsprechen und der Graph wäre dadurch immer zusammenhängend. Ist das so korrekt?
30.01.2017, 12:48	Elvis	Auf diesen Beitrag antworten »
Nein, so ist das nicht. Ein Graph $\begin{eqnarray} G=(V,E) \end{eqnarray}$ ist gegeben, er wird nicht durch mehr oder weniger Kanten verändert, denn sonst entsteht ein anderer Graph. Jedes Paar $\begin{eqnarray} (V1,V2) \end{eqnarray}$ mit $\begin{eqnarray} V=V1\cup V2, V1\cap V2=\emptyset, V1\ne \emptyset, V2\ne\emptyset \end{eqnarray}$ ist eine Bipartition (dt: Zweiteilung) der Knotenmenge. Ein Graph $\begin{eqnarray} G=(V,E) \end{eqnarray}$ heißt bipartit, wenn es eine Bipartition $\begin{eqnarray} V1,V2 \end{eqnarray}$ gibt, so dass keine Kante in $\begin{eqnarray} V1 \end{eqnarray}$ oder $\begin{eqnarray} V2 \end{eqnarray}$ liegt. Diese Definition wird aber für die Aufgabe nicht benötigt.
30.01.2017, 17:35	diego09	Auf diesen Beitrag antworten »
Ok, danke dir nochmal und entschuldige meine Verwirrtheit, aber ich checks dann immer noch nicht wirklich In meinem ersten angehängten Screenshot ganz oben habe ich einen Graph gezeichnet mit 6 Knoten, die oberen drei gelben sind aus V1, die unteren drei türkisen aus V2. V1 und V2 bilden die gesamte Knotenmenge V, des Graphen. Jede Kante besteht aus einem {v1,v2 \| v1 Element V2 und v2 Element V1}, genau wie in der Aufgabenstellung gefordert. Trotzdem ist der Graph nicht zusammenhängend, obwohl ja genau das gezeigt werden soll. Ich verstehe nicht wo hier mein Denkfehler ist.
30.01.2017, 18:24	Elvis	Auf diesen Beitrag antworten »
In deinem ersten Graph wählst Du eine bestimmte Bipartition (V1 oben, V2 unten), für diese gilt die Forderung. Die Forderung gilt nicht für alle Bipartitionen. Sie gilt nicht für die Bipartition, die ich gewählt habe, denn zwischen den 2 linken und den 4 rechten gibt es (politisch korrekt ) keine verbindende Kante. Wenn die Forderung für meine Bipartition nicht gilt, gilt sie nicht für alle Bipartitionen. Weil die Forderung nicht für alle Bipartitionen gilt, ist der Graph nicht zusammenhängend. Logisch gesehen verwechselst Du "es gibt eine BP, für die F gilt; also Z" mit "für alle BP gilt F; also Z" .
Anzeige

30.01.2017, 20:42	diego09	Auf diesen Beitrag antworten »
Aahhh, jetzt hat es endlich geklickt Wie du richtig erkannt hast, hab ich die Grundaussage schon nicht richtig verstanden. Wenn es für alle möglichen Bipartitionen eine Kante {v1,v2} gibt, mit v1 Element V2 und v2 Element V1, ist es auch total logisch dass der Graph zusammenhängend ist. Wie ich das jetzt auch formal beweise, gucke ich mir morgen an Vielen Dank auf jeden Fall, Elvis

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »