matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieEulergraph Beweis
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Graphentheorie" - Eulergraph Beweis
Eulergraph Beweis < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Eulergraph Beweis: Beweis, Hilfe
Status: (Frage) beantwortet Status 
Datum: 11:21 Mo 21.01.2013
Autor: Kartoffelchen

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?

        
Bezug
Eulergraph Beweis: Antwort
Status: (Antwort) fertig Status 
Datum: 12:48 Mi 23.01.2013
Autor: reverend

Hallo Kartoffelchen,

vorab: []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]

> 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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]