Eulergraph Beweis < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie die Äquivalenz:
Ein Graph G ist eulersch <=> Ein Graph G ist zusammenhängend und jeder seiner Knoten ist gerade |
Diese Frage wurde von mir selbst in keinem Forum gestellt außer diesem.
1) Man zeigt, dass G zusammenhängend ist mit geraden Knoten wenn G eulersch ist.
Laut Definition von eulersch besitzt G einen Kreis, der jede Kante von G enthält - genau einmal. Da er ein Kreis ist, sind Start- und Endknoten gleich. Da es zwischen zwei beliebigen Knoten u und v einen Weg gibt, für alle u und v, ist G zusammenhängend.
Da jede Kante einen "Aus" und einen "Ein" - Punkt (Knoten) besitzt, führen von jedem Knoten zwei (oder 4..) Kanten weg -> G hat nur gerade Grade.
2.) Die andere Richtung.-
G ist zusammenhängend, d.h. je zwei Knoten sind in dem Graphen über eine Kette von Kanten erreichbar.
Da G auch eine Gradfolge mit ausschließlich geraden Graden besitzt, gehen von jedem Knoten mindestens 2 Kanten weg, sodass jeder Knoten v von jedem Knoten u aus über mindestens zwei Wege erreicht werden kann.
Da die Grade gerade sind, wird jede Kante einmal durchlaufen.
Könnt ihr mir noch etwas helfen?
|
|
| |
|
Hallo Kartoffelchen,
vorab: ![[]](/images/popup.gif) hier findest Du einen Beweis. Du siehst, dass er nicht ganz so kurz ist...
> Zeigen Sie die Äquivalenz:
> Ein Graph G ist eulersch <=> Ein Graph G ist
> zusammenhängend und jeder seiner Knoten ist gerade
> Diese Frage wurde von mir selbst in keinem Forum gestellt
> außer diesem.
>
> 1) Man zeigt, dass G zusammenhängend ist mit geraden
> Knoten wenn G eulersch ist.
>
> Laut Definition von eulersch besitzt G einen Kreis, der
> jede Kante von G enthält - genau einmal. Da er ein Kreis
> ist, sind Start- und Endknoten gleich. Da es zwischen zwei
> beliebigen Knoten u und v einen Weg gibt, für alle u und
> v, ist G zusammenhängend.
![[ok]](/images/smileys/ok.gif "[ok]")
> Da jede Kante einen "Aus" und einen "Ein" - Punkt (Knoten)
> besitzt, führen von jedem Knoten zwei (oder 4..) Kanten
> weg -> G hat nur gerade Grade.
Das ist nicht gut begründet. Gerade andersherum: im Eulerkreis führt zu jedem durchlaufenen Knoten eine Kante hin und eine weg. Egal wie oft der Knoten im Kreis vorkommt, bleibt sein Grad immer gerade.
> 2.) Die andere Richtung.-
>
> G ist zusammenhängend, d.h. je zwei Knoten sind in dem
> Graphen über eine Kette von Kanten erreichbar.
> Da G auch eine Gradfolge mit ausschließlich geraden
> Graden besitzt, gehen von jedem Knoten mindestens 2 Kanten
> weg, sodass jeder Knoten v von jedem Knoten u aus über
> mindestens zwei Wege erreicht werden kann.
Das ist wahr, aber nicht einsichtig und etwas vorschnell gefolgert.
Falls es Dir nur um den Beweisplan geht: ja, das ist zu zeigen.
> Da die Grade gerade sind, wird jede Kante einmal
> durchlaufen.
Auch das ist zu zeigen: es gibt einen Weg, der jede Kante einmal durchläuft (Eulerweg) und bei dem Anfangs- und Endpunkt zusammenfallen (Eulerkreis).
Ich denke, der Link oben dürfte ausreichen, damit Du den Beweis verstehst.
Grüße
reverend
|
|
|
|
