Beweise Graphentheorie

12.04.2007, 11:11

hmer

Beweise Graphentheorie

Wir beschäftigen uns gerade mit Algorithmen und machen gerade Graphentheorie. Dazu gibt es wieder jede Menge (kleiner) Beweise... was sagt ihr zu meinem "Lösungsansatz" für die folgende Aufgabe?

a) Zeigen Sie, dass ein Baum, der mindestens eine Kante besitzt, auch mindestens zwei Knoten der Valenz 1 enthält.

b) Zeigen Sie, z.B. mittels Ringschluss, dass fürr einen Graphen $\begin{eqnarray*} G = (V, E) \end{eqnarray*}$ mit $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ Knoten die folgenden Aussagen äquivalent sind:
1. G ist ein Baum, d.h. G ist zusammenhängend und enthält keinen Kreis.
2. G ist zusammenhängend und enthält n-1 Kanten.
3. G enthält n-1 Kanten, aber keinen Kreis.
4. G enthält keinen Kreis und bei Hinfügen einer Kante wird genau ein Kreis erzeugt.
5. G ist minimal zusammenhängend, d.h. G ist zusammenhängend und $\begin{eqnarray*} G /e \end{eqnarray*}$ ist nicht zusammenhägend für jede Kante $\begin{eqnarray*} e \in E \end{eqnarray*}$ .
6. Für je zwei Knoten $\begin{eqnarray*} u, v \in V \end{eqnarray*}$ gibt es genau einen [u, v]-Weg in G.

Mein Ansatz für Teil a).

Sei $\begin{eqnarray*} G = (V,E) \end{eqnarray*}$ ein Baum mit $\begin{eqnarray*} |E| \geq 1 \end{eqnarray*}$ . Die Knoten am Ende des längsten Weges im Baum müssen Knoten von Valenz 1 serin.
Sei $\begin{eqnarray*} p = (x_1, x_2,...,x_k) \end{eqnarray*}$ der längste Weg in unserem Baum.

Wir zeigen $\begin{eqnarray*} x_1 \end{eqnarray*}$ ist ein Knoten mit Valenz 1. Nehmen wir an, es gäbe eine weitere Kante $\begin{eqnarray*} x_1z \in E \end{eqnarray*}$ , mit $\begin{eqnarray*} z \neq x_k \end{eqnarray*}$ .

Wäre jetzt $\begin{eqnarray*} z \not \in p, \end{eqnarray*}$ dann könnte man z an p dranhängen und man hätte einen noch längeren Weg. Dies steht im Widerspruch dazu, dass p der längste Weg ist.

Wäre $\begin{eqnarray*} z = x_i \in p, \end{eqnarray*}$ dann wäre $\begin{eqnarray*} k = (x_1,x_2,...,x_i,_x1) \end{eqnarray*}$ ein Kreis => Widerspruch zur Definition Baum.
D.h. der Knoten $\begin{eqnarray*} x_1 \end{eqnarray*}$ hat Grad 1. Gleiches gilt dann auch für $\begin{eqnarray*} x_k \end{eqnarray*}$ .

Bei Teil b) tue ich mir schwerer. Das ist ja ein Ringschluss. Hier mal ein Ansatz für den ersten Schritt.

(1) => (2): Beweis etwa mit Induktion?
Induktionsanfang:
Wenn n = 2 ist, dann muss es eine Kante $\begin{eqnarray*} (n-1) = 2-1 = 1 \end{eqnarray*}$ geben, damit $\begin{eqnarray*} G = (V,E) \end{eqnarray*}$ ein zusammenhängender Graph und damit ein Baum ist.

Induktionsvoraussetzung:
Sei die Aussage für $\begin{eqnarray*} k = n \end{eqnarray*}$ Knoten nun wahr. Sei $\begin{eqnarray*} x_1 \end{eqnarray*}$ nun ein Knoten im Baum mit Valenz 1. Entfernen wir diesen Knoten, dann erhalten wir einen Baum mit n-1 Knoten. Der neue Baum $\begin{eqnarray*} G' = (V / e, E) \end{eqnarray*}$ ist wiederum zusammenhängend, da nur ein Knoten mit Valenz 1 entfernt wurde. Dieser Baum hat auch keinen Kreis, da G auch keinen Kreis hatte.

Nach Induktionsannahme hat G' n-2 Kanten. Der ursprüngliche Baum G hat eine Kante mehr als G', da beim entfernen des Knoten mit Valenz 1 genau eine Kante entfernt wurde. D.h. das G n-1 Kanten hat.

Damit ist doch eigentlich auch schon (3) gezeigt, da der entstehende Baum ja auch keinen Kreis hat... mit minimal zusammenhängend habe ich aber so meine Probleme...

(3) => (4)
Angenommen man hat $\begin{eqnarray*} x,y \in V \end{eqnarray*}$ . Da G zusammenhängend und kreisfrei gibt es einen Weg p von x nach y. Füge man nun eine Kante xy hinzu, so gibt es einen zweiten Weg von x nach y in G und damit also genau einen Kreis.

(4) => (5)
Angenommen $\begin{eqnarray*} G/e \end{eqnarray*}$ für irgendein $\begin{eqnarray*} e \in E \end{eqnarray*}$ , ist zusammenhängend. D.h. zwischen zwei Knoten x,y \in V existiert ein Weg. Wird nun die Kante e wieder hinzugefügt, so entsteht ein Kreis. Dann wäre aber G nicht mehr ein Baum, d.h. Widerspruch. $\begin{eqnarray*} G/e \end{eqnarray*}$ ist nicht zusammenhängend.

(5) => (6)
Annahme: es gibt keinen Weg zwischen zwei Knoten $\begin{eqnarray*} x,y \in V \end{eqnarray*}$ , dann wäre Graph nicht zusammenhängend -> Widerspruch.
Annahme: es gibt mehrere Wege zwischen x,y, dann gäbe es einen Kreis -> Widerspruch.

(6) => (1)
Für je zwei Knoten $\begin{eqnarray*} x,y \in V \end{eqnarray*}$ gibt es genau einen Weg, d.h.G ist zusammenhängend. Angenommen G hätte einen Kreis der durch x,y geht, dann gäbe es zwei verschiedene Wege zwischen x,y -> Widerspruch zur Annahme, es gibt genau einen Weg

Was sagt ihr zu dem versuchten Ringschluss? Vielen dank!

hmer

12.04.2007, 21:28

Abakus

Auf diesen Beitrag antworten »

RE: Beweise Graphentheorie

Zitat:

Original von hmer
a) Zeigen Sie, dass ein Baum, der mindestens eine Kante besitzt, auch mindestens zwei Knoten der Valenz 1 enthält.

Mein Ansatz für Teil a).

Sei $\begin{eqnarray*} G = (V,E) \end{eqnarray*}$ ein Baum mit $\begin{eqnarray*} |E| \geq 1 \end{eqnarray*}$ . Die Knoten am Ende des längsten Weges im Baum müssen Knoten von Valenz 1 serin.
Sei $\begin{eqnarray*} p = (x_1, x_2,...,x_k) \end{eqnarray*}$ der längste Weg in unserem Baum.

Wir zeigen $\begin{eqnarray*} x_1 \end{eqnarray*}$ ist ein Knoten mit Valenz 1. Nehmen wir an, es gäbe eine weitere Kante $\begin{eqnarray*} x_1z \in E \end{eqnarray*}$ , mit $\begin{eqnarray*} z \neq x_k \end{eqnarray*}$ .

Wäre jetzt $\begin{eqnarray*} z \not \in p, \end{eqnarray*}$ dann könnte man z an p dranhängen und man hätte einen noch längeren Weg. Dies steht im Widerspruch dazu, dass p der längste Weg ist.

Wäre $\begin{eqnarray*} z = x_i \in p, \end{eqnarray*}$ dann wäre $\begin{eqnarray*} k = (x_1,x_2,...,x_i,_x1) \end{eqnarray*}$ ein Kreis => Widerspruch zur Definition Baum.
D.h. der Knoten $\begin{eqnarray*} x_1 \end{eqnarray*}$ hat Grad 1. Gleiches gilt dann auch für $\begin{eqnarray*} x_k \end{eqnarray*}$ .

Kann ich nachvollziehen. Mir fehlt allerdings eine Begründung, wieso es einen längsten Weg gibt (eindeutig bestimmt ist der iA nicht).

Zitat:

b) Zeigen Sie, z.B. mittels Ringschluss, dass fürr einen Graphen $\begin{eqnarray*} G = (V, E) \end{eqnarray*}$ mit $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ Knoten die folgenden Aussagen äquivalent sind:
1. G ist ein Baum, d.h. G ist zusammenhängend und enthält keinen Kreis.
2. G ist zusammenhängend und enthält n-1 Kanten.
3. G enthält n-1 Kanten, aber keinen Kreis.
4. G enthält keinen Kreis und bei Hinfügen einer Kante wird genau ein Kreis erzeugt.
5. G ist minimal zusammenhängend, d.h. G ist zusammenhängend und $\begin{eqnarray*} G /e \end{eqnarray*}$ ist nicht zusammenhägend für jede Kante $\begin{eqnarray*} e \in E \end{eqnarray*}$ .
6. Für je zwei Knoten $\begin{eqnarray*} u, v \in V \end{eqnarray*}$ gibt es genau einen [u, v]-Weg in G.

(1) => (2): Beweis etwa mit Induktion?
Induktionsanfang:
Wenn n = 2 ist, dann muss es eine Kante $\begin{eqnarray*} (n-1) = 2-1 = 1 \end{eqnarray*}$ geben, damit $\begin{eqnarray*} G = (V,E) \end{eqnarray*}$ ein zusammenhängender Graph und damit ein Baum ist.

Induktionsvoraussetzung:
Sei die Aussage für $\begin{eqnarray*} k = n \end{eqnarray*}$ Knoten nun wahr. Sei $\begin{eqnarray*} x_1 \end{eqnarray*}$ nun ein Knoten im Baum mit Valenz 1. Entfernen wir diesen Knoten, dann erhalten wir einen Baum mit n-1 Knoten. Der neue Baum $\begin{eqnarray*} G' = (V / e, E) \end{eqnarray*}$ ist wiederum zusammenhängend, da nur ein Knoten mit Valenz 1 entfernt wurde. Dieser Baum hat auch keinen Kreis, da G auch keinen Kreis hatte.

Nach Induktionsannahme hat G' n-2 Kanten. Der ursprüngliche Baum G hat eine Kante mehr als G', da beim entfernen des Knoten mit Valenz 1 genau eine Kante entfernt wurde. D.h. das G n-1 Kanten hat.

Damit ist doch eigentlich auch schon (3) gezeigt, da der entstehende Baum ja auch keinen Kreis hat... mit minimal zusammenhängend habe ich aber so meine Probleme...

Induktion sieht recht umständlich aus. Dass es mindestens (n-1) Kanten sein müssen, ist klar (ansonsten wären die n Knoten nicht zusammenhängend). Dass es höchstens (n-1) Kanten sind, kannst du sicher auch begründen.

(2) => (3) fehlt noch

Zitat:

(3) => (4)
Angenommen man hat $\begin{eqnarray*} x,y \in V \end{eqnarray*}$ . Da G zusammenhängend und kreisfrei gibt es einen Weg p von x nach y. Füge man nun eine Kante xy hinzu, so gibt es einen zweiten Weg von x nach y in G und damit also genau einen Kreis.

Das würde mir nicht reichen. Es könnte ja mehr als nur einen Kreis geben, wieso also gibt es genau einen ?

Zitat:

(4) => (5)
Angenommen $\begin{eqnarray*} G/e \end{eqnarray*}$ für irgendein $\begin{eqnarray*} e \in E \end{eqnarray*}$ , ist zusammenhängend. D.h. zwischen zwei Knoten x,y \in V existiert ein Weg. Wird nun die Kante e wieder hinzugefügt, so entsteht ein Kreis. Dann wäre aber G nicht mehr ein Baum, d.h. Widerspruch. $\begin{eqnarray*} G/e \end{eqnarray*}$ ist nicht zusammenhängend.

Zunächst, wieso ist G überhaupt zusammenhängend ? (das musst du auch zeigen)

Zitat:

(5) => (6)
Annahme: es gibt keinen Weg zwischen zwei Knoten $\begin{eqnarray*} x,y \in V \end{eqnarray*}$ , dann wäre Graph nicht zusammenhängend -> Widerspruch.
Annahme: es gibt mehrere Wege zwischen x,y, dann gäbe es einen Kreis -> Widerspruch.

(6) => (1)
Für je zwei Knoten $\begin{eqnarray*} x,y \in V \end{eqnarray*}$ gibt es genau einen Weg, d.h.G ist zusammenhängend. Angenommen G hätte einen Kreis der durch x,y geht, dann gäbe es zwei verschiedene Wege zwischen x,y -> Widerspruch zur Annahme, es gibt genau einen Weg

Ja, ok.

Grüße Abakus smile

12.04.2007, 23:13

Tobias

Auf diesen Beitrag antworten »

Zitat:

Kann ich nachvollziehen. Mir fehlt allerdings eine Begründung, wieso es einen längsten Weg gibt (eindeutig bestimmt ist der iA nicht).

Wenn hmer "der längste Weg" durch "ein längster Weg" ersetzt ist sein Beweis zu 1) m.E. richtig da man tatsächlich nur irgendeinen längsten Weg braucht. Wir reden nur von endlichen Graphen also gibt es immer mindestens einen längsten Weg in jedem Graphen.

Um die Induktion zu vermeiden könnte man verwenden, dass die zyklomatische Zahl |E| - |V| + #Zusammenhangskomponenten in einem Baum 0 ist. Wenn man das nicht verwenden darf finde ich die Induktion recht elegant.

Bei deinem Ringschluss musst du aufpassen, dass du die Voraussetzungen richtig benutzt, sonst könntest du die Äquivalenzen zerstören.

15.04.2007, 14:15

hmer

Auf diesen Beitrag antworten »

Hallo.

also ich finde induktion da gar nicht so schlecht... von a) weiß ich ja, dass wenn ich einen baum habe, dieser mindestens zwei blätter hat. wenn ich jetzt ein blatt entferne, dann habe ich entweder keinen baum mehr (nur einen knoten), oder aber wiederum immer noch ein baum.

bei "(2) => (3)" meine ich, dass das schon im induktionsbeweis gezeigt ist, oder?

schließlich hat der baum mit n-1 kanten auch keinen kreis, da ja nur ein blatt entfernt wurde...

bei den anderen argumenten (3) => (4), (4) => (5) stehe ich auf dem schlauch: wie kann ich denn zeigen, dass es genau einen kreis gibt?

vielleicht sollte ich das doch eher nicht mit ringschluss versuchen und einzeln zeigen...

15.04.2007, 21:47

hmer

Auf diesen Beitrag antworten »

hmm...

hat niemand noch eine idee oder tip?

beim direkten weg müsste ich doch immer nur (1) => (2) und dann (2) => (1) zeigen...

aber dann sind das wohl recht viele teilschritte...

16.04.2007, 01:15

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von hmer
bei "(2) => (3)" meine ich, dass das schon im induktionsbeweis gezeigt ist, oder?

schließlich hat der baum mit n-1 kanten auch keinen kreis, da ja nur ein blatt entfernt wurde...

Also so aus dem Zusammenhang gerissen, lässt sich da weder ja noch nein zu sagen. Das ist doch völlig unübersichtlich, was die Voraussetzungen nun sind und was gezeigt wurde.

Bemühe dich lieber um einen klaren und eindeutigen Beweisstil.

Zitat:

bei den anderen argumenten (3) => (4), (4) => (5) stehe ich auf dem schlauch: wie kann ich denn zeigen, dass es genau einen kreis gibt?

Du hast ja schon überlegt, dass es im Baum von x nach y genau einen Weg gibt. Nun musst du überlegen, wie durch eine weitere Kante der Kreis zustande kommt und ob weitere Kreise zustande kommen können.

Zitat:

vielleicht sollte ich das doch eher nicht mit ringschluss versuchen und einzeln zeigen...

Ja, könntest du auch. Ein Ringschluss ist allerdings schön effizient.

Grüße Abakus smile

16.04.2007, 11:57

Tobias

Auf diesen Beitrag antworten »

Du kannst auch erste einen kleinen Ringschluss machen:

(1) => (2) => (3) => (1)

Wenn du jetzt z.B. (3) => (4) beweisen willst, kannst du die Voraussetzungen von (1) und (2) mitbenutzen.

17.04.2007, 17:28

hmer

Auf diesen Beitrag antworten »

ok...ich versuch das jetztnoch mal in ruhe schritt für schritt durchzugehen...

aber ich meine, dass die Induktion so schlüssig ist (ist vielleicht nicht klar genug aufgeschrieben). Aber ich kann auf den Satz zurückgreifen, dass ein Baum mindestents zwei Knoten von Valenz 1 hat...

(1) G ist ein Baum, d.h. er ist zusammenhängend und hat keinen Kreis.

=> (2) G ist zusammenhängend und enthält n-1 Kanten.

Induktionsanfang:
Für n = 2 ist die Aussage wahr, denn damit G = (V,E) zusammenhängend und kreisfrei ist, ist eine Kante zwischen den beiden Knoten notwendig.

Induktionsannahme:
Die Behauptung sei für einen Baum G mit k = n-1 Knoten erfüllt.

Induktionsschritt:

(1) => (2) und (3):
Sei G=(V,E) ein Baum mit n Knoten. Dann hat dieser Baum mindestens zwei Knoten von Valenz 1. Entfernt man einen dieser Knoten und die dazugehörige Kante, dann erhält man einen Graphen G' mit n-1 Knoten. Da nur ein Knoten mit Valenz 1 entfernt wurde, ist auch G' zusammenhängend und hat keinen Kreis, da schon G keinen Kreis hatte. Nach Induktionsannahme hat G' genau n-2 Kanten. G hat eine Kante mehr als G', da beim entfernen des Knoten mit Grad 1 genau eine Kante entfern wurde => G hat genau n-1 Kanten, die Aussage gilt auch für n Knoten.

Was meint ihr zu der Induktion?

17.04.2007, 21:26

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von hmer
(1) G ist ein Baum, d.h. er ist zusammenhängend und hat keinen Kreis.

=> (2) G ist zusammenhängend und enthält n-1 Kanten.

Induktionsanfang:
Für n = 2 ist die Aussage wahr, denn damit G = (V,E) zusammenhängend und kreisfrei ist, ist eine Kante zwischen den beiden Knoten notwendig.

Was machst du mit n=0 oder n=1 ? (hier reicht ein Satz, um das noch abzuhandeln)

Zitat:

Induktionsannahme:
Die Behauptung sei für einen Baum G mit k = n-1 Knoten erfüllt.

Du brauchst die Induktionsvoraussetzung für alle Bäume mit k=n-1 Knoten. Außerdem musst du noch festlegen, dass n >= 2 sein muss.

Zitat:

Induktionsschritt:

(1) => (2) und (3):
Sei G=(V,E) ein Baum mit n Knoten. Dann hat dieser Baum mindestens zwei Knoten von Valenz 1. Entfernt man einen dieser Knoten und die dazugehörige Kante, dann erhält man einen Graphen G' mit n-1 Knoten. Da nur ein Knoten mit Valenz 1 entfernt wurde, ist auch G' zusammenhängend und hat keinen Kreis, da schon G keinen Kreis hatte. Nach Induktionsannahme hat G' genau n-2 Kanten. G hat eine Kante mehr als G', da beim entfernen des Knoten mit Grad 1 genau eine Kante entfern wurde => G hat genau n-1 Kanten, die Aussage gilt auch für n Knoten.

Wieso G ? Diese Bezeichnung ist bei der Induktionsannahme schon verwendet.

Ansonsten ok.

Grüße Abakus smile

Neue Frage »

Antworten »

Beweise Graphentheorie

Verwandte Themen