Zusammenhang, einf. Graph < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei G ein einfacher Graph (d.h. ohne Schlingen oder mehrfachen Kanten) mit n Knoten, und sei für je zwei Knoten [mm] v_{1}, v_{2}, [/mm] die nicht durch eine Kante verbunden sind, die Summe ihrer Grade
mindestens n - 1
Zeige: G ist zusammenhängend |
Hallo, ich habe vorher das Beispiel zu lösen versucht, auch erfolgreich wie mir scheint, bin allerdings noch ein wenig unsicher auf dem Gebiet der Graphen, und würde daher um eine Korrekturlesung meines Beweises bitten.
Im folgeden bezeichne d(v) den Grad eines Knoten, d.h. die Anzahl aller Kanten e , für die gilt, dass v [mm] \in [/mm] e
Da der Graph einfach ist, entspricht d(v) der Anzahl der Knoten, mit denen v durch eine Kante verbunden ist.
Sei außerdem V(G) die Menge der Knoten von G, und E(G) die Menge der Kanten von G.
Um zu zeigen, dass G zusammenhängend ist, muss also für je zwei Knoten [mm] v_{1}, v_{2} [/mm] eine Wanderung, die in G liegt, gefunden werden, welche die beiden Knoten verbindet.
Sei [mm] V_{i} [/mm] = {w [mm] \in [/mm] V(G) | [mm] \exists [/mm] e [mm] \in [/mm] E(G): [mm] v_{i} \in [/mm] e und w [mm] \in [/mm] e}
Man kann annehmen, dass [mm] V_{1} [/mm] und [mm] V_{2} [/mm] disjunkt sind, sonst wären [mm] v_{1} [/mm] und [mm] v_{2} [/mm] bereits über einen Zwischenknoten verbunden.
Auch kann angenommen werden, dass [mm] d(v_{i}) \ge [/mm] 1 für i [mm] \in [/mm] {1,2}, denn hätte einer der beiden Knoten Grad n-1, so wäre er bereits mit allen anderen Knoten verbunden, und der Graph wäre zusamenhängend.
[mm] v_{1} [/mm] und [mm] v_{2} [/mm] initieren Zusammenhangskomponenten [mm] K_{1} [/mm] bzw. [mm] K_{2} [/mm] von G, mit je mindestens [mm] d(v_{i}) [/mm] + 1 Knoten (i [mm] \in [/mm] {1,2}).
Wären [mm] K_{1} [/mm] und [mm] K_{2} [/mm] disjunkt, so hätte hätte G also mindestens
[mm] d(v_{1}) [/mm] + 1 + [mm] d(v_{2}) [/mm] +1 = n - 1 + 2 Knoten
Ein Widerspruch, dazu, dass G n Knoten hat. Also ist G zusammenhängend.
Danke für alle Antworten.
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:42 Mi 25.06.2008 | | Autor: | koepper |
Guten Morgen,
> Sei G ein einfacher Graph (d.h. ohne Schlingen oder
> mehrfachen Kanten)
solche Graphen nennt man auch "schlicht"
> mit n Knoten, und sei für je zwei Knoten
> [mm]v_{1}, v_{2},[/mm] die nicht durch eine Kante verbunden sind,
> die Summe ihrer Grade
> mindestens n - 1
> Zeige: G ist zusammenhängend
> Hallo, ich habe vorher das Beispiel zu lösen versucht,
> auch erfolgreich wie mir scheint, bin allerdings noch ein
> wenig unsicher auf dem Gebiet der Graphen, und würde daher
> um eine Korrekturlesung meines Beweises bitten.
>
> Im folgeden bezeichne d(v) den Grad eines Knoten, d.h. die
> Anzahl aller Kanten e , für die gilt, dass v [mm]\in[/mm] e
> Da der Graph einfach ist, entspricht d(v) der Anzahl der
> Knoten, mit denen v durch eine Kante verbunden ist.
> Sei außerdem V(G) die Menge der Knoten von G, und E(G) die
> Menge der Kanten von G.
>
> Um zu zeigen, dass G zusammenhängend ist, muss also für je
> zwei Knoten [mm]v_{1}, v_{2}[/mm] eine Wanderung, die in G liegt,
> gefunden werden, welche die beiden Knoten verbindet.
>
> Sei [mm]V_{i}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
= {w [mm]\in[/mm] V(G) | [mm]\exists[/mm] e [mm]\in[/mm] E(G): [mm]v_{i} \in[/mm] e
> und w [mm]\in[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
e}
>
> Man kann annehmen, dass [mm]V_{1}[/mm] und [mm]V_{2}[/mm] disjunkt sind,
> sonst wären [mm]v_{1}[/mm] und [mm]v_{2}[/mm] bereits über einen
> Zwischenknoten verbunden.
>
> Auch kann angenommen werden, dass [mm]d(v_{i}) \ge[/mm] 1 für i [mm]\in[/mm]
> {1,2}, denn hätte einer der beiden Knoten Grad n-1, so wäre
> er bereits mit allen anderen Knoten verbunden, und der
> Graph wäre zusamenhängend.
>
> [mm]v_{1}[/mm] und [mm]v_{2}[/mm] initieren Zusammenhangskomponenten [mm]K_{1}[/mm]
> bzw. [mm]K_{2}[/mm] von G, mit je mindestens [mm]d(v_{i})[/mm] + 1 Knoten (i
> [mm]\in[/mm] {1,2}).
> Wären [mm]K_{1}[/mm] und [mm]K_{2}[/mm] disjunkt, so hätte hätte G also
> mindestens
> [mm]d(v_{1})[/mm] + 1 + [mm]d(v_{2})[/mm] +1 = n - 1 + 2 Knoten
nur eine kleine Ungenauigkeit hier:
Du verwendest in der Gleichung [mm] $d(v_1) [/mm] + [mm] d(v_2) [/mm] = n - 1$.
Nach Voraussetzung ist aber [mm] $d(v_1) [/mm] + [mm] d(v_2) \ge [/mm] n - 1$.
Das Wort "mindestens" davor reicht nicht, das zu heilen.
Mein Vorschlag:
Wären [mm] $K_1$ [/mm] und [mm] $K_2$ [/mm] disjunkt, so wäre wegen [mm] $d(v_1) [/mm] + [mm] d(v_2) \ge [/mm] n - 1$:
$|V| = n [mm] \ge d(v_1) [/mm] + 1 + [mm] d(v_2) [/mm] + 1 [mm] \ge [/mm] n - 1 + 2$, also $n [mm] \ge [/mm] n + 1$.
> Ein Widerspruch, dazu, dass G n Knoten hat. Also ist G
> zusammenhängend.
>
> Danke für alle Antworten.
>
> Ich habe diese Frage in keinem anderen Forum gestellt.
>
|
|
|
|
