semi-eulersche Graphen

Neue Frage »

Maesta Auf diesen Beitrag antworten »
semi-eulersche Graphen
Hallo. Hoffe mir kann bei dieser Aufgabe jemand behilflich sein...

Es ist zu beweisen, dass ein zusammenhängender Graph G genau dann semi-eulersch ist, wenn höchstens zwei Knoten von G ungeraden Grad haben.

Hab dies als Folgerung in mehreren Büchern gefunden, aber immer ohne Beweis.
Irrlicht Auf diesen Beitrag antworten »

Gib uns mal deine Definitionen von "zusammenhängender Graph", "semi-eulerscher Graph" und "Grad eines Knoten". Dann können wir gemeinsam einen Beweis überlegen.
m00xi Auf diesen Beitrag antworten »

Zitat:
Original von Irrlicht
Gib uns mal deine Definitionen von "zusammenhängender Graph", "semi-eulerscher Graph" und "Grad eines Knoten". Dann können wir gemeinsam einen Beweis überlegen.


@Irrlicht: zusammenhängend heißt, dass es zwischen 2 beliebigen Punkten einen Pfad gibt. Der Grad eines Knotens sind ist die Anzahl der inzidenten Kanten ( Kanten, die in diesem Punkt enden oder anfangen ).
Und ich denke, dass ein Graph semi-eulersch ist, wenn es eine Tour durch alle Kanten des Graphen gibt, die aber kein Zyklus ist und man bei einem anderen Knoten endet als man gestartet ist.
Irrlicht Auf diesen Beitrag antworten »

M00xi, DICH HAB ICH NICHT GEFRAGT! Definitionen sind nicht immer gleich!! Deshalb brauch ich die Definitionen des Fragestellers und nicht deine. (Im übrigens weiss ich auch, was zusammenhängend heisst...)
m00xi Auf diesen Beitrag antworten »

Huch *vordemkopfgestoßenfühlt* naja t'schuldigung, ich dachte eben ich könne Helfen, konnte ja nicht wissen, dass du das selber weißt.
:rolleyes: :rolleyes: :rolleyes: :rolleyes:
Irrlicht Auf diesen Beitrag antworten »

Und selbst wenn ich es nicht gewusst hätte: Ich hab Maesta gefragt, nicht dich! Was ist der Unterschied zwischen "Was ist die Definition von...?" und "Was ist deine Definition von...?"? Du musst halt noch lernen, wo du helfen kannst, und wo nicht.
Zurück zum Thema...

Maesta, schreibst du bitte deine Definionen dieser Begriffe auf?
 
 
Maesta Auf diesen Beitrag antworten »

zusammenhängend ist ein Graph G, falls es zu jedem Punkt v,w einen Weg von v nach w in G gibt
Der Grad einen Knotens v ist die Anzahl der mit v inzidenten Kanten.
Ein Graph G heißt semi-eulersch, falls es einen Pfad gibt, der jede Kanten e genau einmal benutzt. Ein solcher Pfad heißt Eulerpfad.
SirJective Auf diesen Beitrag antworten »

Die anschauliche Erklärung ist die, dass ein Eulerpfad die Knoten, in die er hineinkommt, auch wieder verlassen muss (mit Ausnahme von Start- und Endknoten). Damit muss jeder außer dem Start- und Endknoten einen geraden Grad haben. Und natürlich muss er zusammenhängend sein (oder höchstens isolierte Knoten haben), weil sonst nicht alle Kanten erreichbar wären.
Aber wie kommt man auf die Umkehrung, also dass ein zusammenhängender Graph mit höchstens zwei ungeraden Knoten einen Eulerpfad hat...

Einen Beweis hab ich hier gefunden:
http://www.zaik.uni-koeln.de/AFS/teachin...pt/Kapitel4.pdf

Die Idee ist folgende: Wenn alle Knoten geraden Grad haben, ist er eulersch (noch zu zeigen), also auch semi-eulersch. Andernfalls hat er genau zwei Knoten mit ungeradem Grad. Die verbinden wir mit einer zusätzlichen Kante. Damit haben alle Knoten geraden Grad und der neue Graph ist eulersch. Entfernen wir aus dem geschlossenen Eulerpfad dieses Graphen die Zusatzkante, erhalten wir unseren gesuchten offenen Eulerpfad.

Die Frage bleibt also, warum jder zusammenhängende Graph, in dem alle Knoten geraden Grad haben, einen Eulerpfad hat. Das wird in dem Dokument mit vollständiger Induktion nach der Anzahl der Kanten gemacht. Als Hilfssatz wird dabei benötigt, dass jeder solche Graph einen Kreis enthält (also eine geschlossene Kantenfolge).

Wenn du noch Fragen zu dem Beweis in dem Text hast, kannst du sie gern hier stellen, Maesta.
Und du, m00xi, natürlich auch smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »