[Graphentheorie] Wo liegt der Fehler im Beweis?

15.10.2010, 18:23

Spreech

[Graphentheorie] Wo liegt der Fehler im Beweis?

Hallo zusammen,

ich stehe gerade vor folgendem Beweis:

Sei G = (V,E) ein ungerichteter Graph mit |V| = n.
Zeige: Wenn für jeden Knoten v € V gilt: deg(v) >= 1/2 (n-1), dann ist G zusammenhängend.

Was ich weiß:

Wenn |E| >= |V| -1 ist, dann ist G zusammenhängend.

Weiterhin weiß ich, dass die Summe aller Grade der doppelten Anzahl der Kanten entsprechen muss.

Die Summe aller Grade der Knoten kann ich in diesem Beispiel ja als
n * 1/2(n-1) berechnen, d.h.
Summe aller Grade = 2|E| >= n*1/2(n-1) sein.

=> |E| >= 1/4 n² - 1/4 n sein muss.

Jetzt sehe ich allerdings, dass 1/4 n² - 1/4 n nur >= n-1 ist für n>= 4.

Das würde ja im Umkehrschluss bedeuten, dass die Behauptung für n<4 nicht gilt.
Dies macht wiederum keinen Sinn, da ja bspw. jeder Knoten bei n=3 einen Grad von 1 hat und die Knoten daher zusammenhängend sein müssen (es gibt zwei Kanten).

Kann mir vielleicht jemand weiterhelfen wo mein Denkfehler liegt?

Danke im Voraus,

Spreech

15.10.2010, 19:05

Abakus

Auf diesen Beitrag antworten »

RE: [Graphentheorie] Wo liegt der Fehler im Beweis?

Zitat:

Original von Spreech
Was ich weiß:

Wenn |E| >= |V| -1 ist, dann ist G zusammenhängend.

Hallo!

Kannst du begründen, wieso das gelten soll? Allgemein gilt das ja nicht, vielleicht fehlt einfach nur das Argument.

Ansonsten ist A folgt B natürlich nicht gleichbedeutend mit B folgt A (zu deinem Umkehrschluß).

Grüße Abakus smile

15.10.2010, 20:34

Spreech

Auf diesen Beitrag antworten »

Ach super, klar, da liegt der Fehler begraben... Danke für den Hinweis!

Hatte auch anfangs etwas verwechselt.

Es muss heißen:
Wenn G zusammenhängend ist, dann gilt |E| >= |V| -1 ist.

Ich habe mir nun einen anderen Gedankenzug überlegt und komme da auch zum richtigen Ergebnis.
Vielleicht kann da dennoch nochmals jemand drüber kucken ob man das so schreiben kann (sind meine ersten Beweise überhaupt...).

Sei G ein Graph für welchen die Behauptung gilt.
Dann muss die Gesamtanzahl der Grade >= 1/2n^2-1/2n sein.
Da die Gesamtanzahl der Grade 2*|E| entspricht folgt daraus, dass |E| >= 1/4n²-1/4n sein muss.

Ich betrachte nun einen Graphen H der genau einen Knoten mehr hat als G und G soll ein Teilgraph von H sein.
Nun müsste also für jeden Knoten gelten, dass er einen Grad von >= 1/2n hat.
Demnach müsste die Gesamtanzahl der Grade 1/2n^2+1/2n sein woraus |E| >= 1/4n²+1/4n folgt.

Es ist also zu erkennen, dass die Differenz der Kantenanzahl mind. n betragen muss, wenn n Knoten dazukommen.
Dies ist auch intuitiv, denn jeder Knoten der hinzukommt braucht mind. eine Kante zu den bisherigen Knoten, damit auch der "neue" Graph noch vollständig ist.

Ist wohl absolut nicht die feine mathematische Art wie ich das beschreibe, aber vielleicht kann man meinen Gedankenzug nachvollziehen...

Danke im Voraus für Euer Feedback und Euch noch einen schönen Abend!

Gruß

16.10.2010, 12:08

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Spreech
Sei G ein Graph für welchen die Behauptung gilt.

Du meinst die Voraussetzung soll gelten?

Zitat:

Dann muss die Gesamtanzahl der Grade >= 1/2n^2-1/2n sein.
Da die Gesamtanzahl der Grade 2*|E| entspricht folgt daraus, dass |E| >= 1/4n²-1/4n sein muss.

OK.

Zitat:

Ich betrachte nun einen Graphen H der genau einen Knoten mehr hat als G und G soll ein Teilgraph von H sein.

Wozu? Wenn das eine Induktion über die Knotenanzahl werden soll, kündige das genau an.

Zitat:

Nun müsste also für jeden Knoten gelten, dass er einen Grad von >= 1/2n hat.
Demnach müsste die Gesamtanzahl der Grade 1/2n^2+1/2n sein woraus |E| >= 1/4n²+1/4n folgt.

Wieso müsste das Erste gelten? Das ist vorausgesetzt und nicht gefolgert.

Zitat:

Es ist also zu erkennen, dass die Differenz der Kantenanzahl mind. n betragen muss, wenn n Knoten dazukommen.

Welche Differenz genau? Und n Knoten kommen ja nicht dazu.

Zitat:

Dies ist auch intuitiv, denn jeder Knoten der hinzukommt braucht mind. eine Kante zu den bisherigen Knoten, damit auch der "neue" Graph noch vollständig ist.

Vollständig würde heißen, dass alle Kanten vorhanden sind. Hier ging es um Zusammenhang.

Insgesamt: ich sehe da keine klare Linie in deinem Beweis.

Grüße Abakus smile

22.10.2010, 22:06

Spreech

Auf diesen Beitrag antworten »

bin da wohl ein wenig durcheinander gekommen mit zusammenhängend und vollständig...

Habe nun den "Musterbeweis" bekommen und kann es nachvollziehen - besten Dank für deine Rückmeldung.

20.11.2011, 20:43

Graphi

Auf diesen Beitrag antworten »

Wäre denn hier Induktionsbeweis oder ein indirekter Beweis einfacher?

Ich komme bei dieser Aufgabe leider nicht zum Ziel. :-/