Zusammenhängend? < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:53 Mi 07.05.2008 | | Autor: | Biggles |
| Aufgabe | Sei G = (V,E) Graph, |V| = n und |E| > [mm] \frac{(n-1)(n-2)}{2}
[/mm]
Zeigen Sie, G ist zusammenhängend
|
Hallo
Ich habe das mal für kleine n gezeichnet und es ist mir anschaulich total klar, nur die Beweisidee fehlt. Ich wollte zunächst den Beweis verwenden, dass ein zusammenhängender Graph mit n Knoten und n-1 Kanten ein Baum ist, aber das passt hier ja nicht so richtig, obwohl ich denke, da sind ein paar richtige Sachen dabei.
Jedenfalls bin ich hier überfordert, kann mich jemand auf die richtige Spur bringen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:46 Mi 07.05.2008 | | Autor: | MacMath |
Angenommen G ist nicht zusammenhängend, dass muss....... gelten.
(Rechnen)
Dann kann die Forderung nicht erfüllt werden. Also ist G zusammenhängend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:14 Mi 07.05.2008 | | Autor: | Biggles |
| Aufgabe | Sei G = (V,E) Graph, |V| = n und |E| > $ [mm] \frac{(n-1)(n-2)}{2} [/mm] $
Zeigen Sie, G ist zusammenhängend |
Hallo MacMath. Die Antwort im anderen Thema hat mich gut vorangebracht. Dankeschön
Aber hier verstehe ich nicht, worum es geht
> Angenommen G ist nicht zusammenhängend, dass muss.......
> gelten.
> (Rechnen)
>
> Dann kann die Forderung nicht erfüllt werden. Also ist G
> zusammenhängend
Außer, dass ich jetzt einen Widerspruchsbeweis machen soll, ist mir nichts klarer geworden. Leider.
Also ich könnte mir jetzt nur vorstellen
Angenommen G ist nicht zusammenhängend, dann muss G mit |V| = n gelten, dass |E| < n-1. Denn dann können n Knoten ja nicht mehr miteinander verbunden werden.
Das hat jetzt aber leider nichts mit |E| > $ [mm] \frac{(n-1)(n-2)}{2} [/mm] $ zu tun, sodass ich doch nicht weiterkomme.
Grüße
Biggles
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:04 Do 08.05.2008 | | Autor: | MacMath |
*g* Bist du dir sicher? Die Frage ist doch eher: Wie viele Knoten kannst du höchstens miteinander verbinden...
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 07:50 Do 08.05.2008 | | Autor: | Biggles |
| Aufgabe | Sei G = (V,E) Graph, |V| = n und |E| > $ [mm] \frac{(n-1)(n-2)}{2} [/mm] $
Zeigen Sie, G ist zusammenhängend |
Hi.
> *g* Bist du dir sicher? Die Frage ist doch eher: Wie viele
> Knoten kannst du höchstens miteinander verbinden...
Wenn |E| = $ [mm] \frac{(n-1)(n-2)}{2} [/mm] $, dann können $ [mm] \frac{(n-1)(n-2)}{2} [/mm] -1$ Knoten verbunden werden, höchstens. Und wenn
|E| = $ [mm] \frac{(n-1)(n-2)}{2} [/mm] +1$ dann können höchstens $ [mm] \frac{(n-1)(n-2)}{2} [/mm] $ miteinander verbunden werden.
Also bei n Knoten sind schon mindestens n-1 Kanten notwendig.
Ich bin dir wirklich dankbar für deine Hilfe, aber ich habe das Gefühl, dass deine Ratschläge etwas zu kurz für mich sind und ich das so nie hinkriege :(
Biggles
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:28 Fr 09.05.2008 | | Autor: | koepper |
Hallo Biggles,
wie der Vorsatz "Mac" schon sagt... er ist etwas geizig mit seinen Hinweisen, die hier auch nicht zur Lösung führen 
Wir brauchen als zusätzliche Voraussetzung hier, daß es sich bei G um einen sogenannten "schlichten" Graphen handelt. Ein schlichter Graph hat keine parallelen Kanten und keine Schlingen. Ihr habt in der Vorlesung wahrscheinlich vereinbart, daß alle betrachteten Graphen - soweit nicht ausdrücklich anders gesagt - schlicht sein sollen.
Nimm zunächst an, G sei nicht zusammenhängend. Dann zerfällt G in (mindestens) 2 Komponenten. Eine dieser Komponenten [mm] $G_1$ [/mm] habe a Knoten (mit 0 < a < n). Wir überlegen nun, wie viele Kanten ein solcher Graph maximal haben kann. Zu einem (schlichten) Graphen können so lange Kanten hinzugefügt werden, bis alle Knoten paarweise miteinander verbunden sind. Ein solcher Graph heißt "vollständig". Man sieht leicht, daß ein vollständiger Graph mit a Knoten genau ${a [mm] \choose [/mm] 2} = [mm] \frac{a * (a-1)}{2}$ [/mm] Kanten hat. Selbst wenn $G - [mm] G_1$ [/mm] vollständig ist, kann G damit maximal
[mm] $\frac{a * (a-1)}{2} [/mm] + [mm] \frac{(n-a) * (n-a-1)}{2} [/mm] = [mm] \frac{n * (n-1)}{2} [/mm] - a * (n-a)$
Kanten haben. Dieser Wert wird für $a = 1$ oder $a = n - 1$ maximal. Da die erzielten Werte gleich groß sind reicht es, a = 1 näher zu betrachten. Durch Einsetzen erhalten wir einen maximalen Wert von
[mm] $\frac{n * (n-1)}{2} [/mm] - (n-1) = [mm] \frac{n * (n-1) - 2(n-1)}{2} [/mm] = [mm] \frac{(n-2) * (n-1)}{2}$ [/mm] Kanten.
LG
Will
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:19 Fr 09.05.2008 | | Autor: | Biggles |
Hallo.
Vielen Dank für deine Antwort, genau so etwas hatte ich mir erhofft, dankeschön
Grüße,
Biggles
|
|
|
|
