Eulerscher Kantenzug

Melvin · Anmeldungsdatum: 24.05.2005 Beiträge: 5

Hallo,

ich habe eine Aufgabe, wo ich nicht weiss, wie ich die Aufgabe angehen soll.
Kann einer mir bitte helfen??

Die Aufgabenstellung:

Es sei G= (V,E) ein zusammenhängender, gerichteter Graph. Ein Eulerscher Kantenzug besteht aus einem Kreis, der jede Kante in E genau einmal durchläuft. Dagegen dürfen die einzelnen Knoten durch aus mehrfach durchlaufen werden.
Zeigen Sie, dass G genau dann einen Eulerschen Kantenzug enthält, fals für alle Knoten v Element aus V gilt:
Eingangsgrad(v) = Ausgangsgrad.

Ich verstehe die Aufgabenstellung und kenne auch die Begriffe: zusammenhängender, gerichteter Graph; Eingangs- und Ausgangsgrad.
Aber ich weiss nicht, wie den Beweis durch führt.
Es wäre sehr nett, wenn einer mir einen Tip geben könnte.

Danke!
Gruß
Melvin

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Melvin · Anmeldungsdatum: 24.05.2005 Beiträge: 5

Hallo,

ich weiss aber nicht, wie der Beweis genau aussehen soll.
Kann man denn etwa so machen:

--> Wenn der Eingangsgrad = Ausgangsgrad ist, muß also an jedem Punkt
ankommende Kante auch diesen Punkt verlassen. Da dieser Graph ein zusammenhängender, gerichteter Graph ist, kommt man, da man einen Kanten nur einmal durchlaufen darf wieder zum Anfangsknoten, da beim diesem ja eine
Kante vom Knoten weggeht, aber nicht hinführt:

Kann man so ungefähr machen??

Die Rückrichtung kriege ich nicht hin.

Kannst du mir hierbei helfen?

Danke

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Die Rückrichtung ist einfacher:

Nimm an es gäbe einen Eulerkreis im Digraphen G. Da jede Kante im Kreis etabliert ist und der Graph zusammenhängend ist, muss also auch jede Ecke am Kreis partizipieren. Durchlaufe nun einfach den Kreis. Was stellst du fest?

Die andere Richtung, in der du "Eingangsgrad = Ausgangsgrad" annimmst ist ein bisschen komplizierter und könnte z.B. durch Induktion gelöst werden. Da der Graph zusammenhängend ist, existiert für jede Ecke ein Eingangsgrad von mind. 1 und somit auch ein Ausgangsgrad von mind. 1. Dieser Graph hat auf jeden Fall einen Kreis zugesichert.

[Das folgt aus einem Satz:
Ist D ein Digraph und es gilt
max{min{Ausgangsgrade}, min{Eingangsgrade}} > 0
dann hat D einen orientierten Kreis. ]

Dieser Kreis in G möge C sein. Jetzt entfernen wir alle Kanten aus G, die in C vorkommen und nennen den Differenzgraph G'. besitzt G' keine Kanten mehr, dann war C schon der gesuchte Eulerkreis. Hat G' allerdings noch Kanten, dann besitzen alle Ecken in G' noch die Eigenschaft Eingangsgrad = Ausgangsgrad. Somit lässt sich nun auf jede Zusammenhangskomponente von G' die Induktionsvoraussetzung anwenden, die besagt, dass jede Komponente einen Eulerkreis besitzt. Dank des Zusammenhangs hat mindestens jeweils eine Ecke der Zusammenhangskomponenten eine gemeinsame Ecke mit dem Kreis C. Daraus konstruieren wir den Eulerkreis.

Hoffe, die Idee ist klar geworden.

Melvin · Anmeldungsdatum: 24.05.2005 Beiträge: 5

Hallo,

ich verstehe einiges in deinem Beweis nicht.
Meinst du mit Ecke, Knoten?

Wie soll hier eine Induktionsbeweis durchgeführt werden?
Was kann ich denn Induktionsannahme nehmen?
Den Satz den du angewandt hast, haben wir aber noch nicht gehabt!!

Kannst du mir bitte noch mals anders erklären?

danke!!

Gruß
Melvin