Beweis zu eulerschen Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeige, dass ein Graph G = (V, E, phi) genau dann ein Kreis ist, wenn G ein eulerscher Graph mit der Eigenschaft, dass der Untergraph [mm] G_e [/mm] = (V, E \ {e}, phi|e \ {e}) für jede Kante e € E ein Baum ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hey,
ich hätte einige Fragen zur obigen Aufgabenstellung.
Mir fehlt hier der komplette Ansatz, wie ich diesen Beweis führen soll.
Was ich weiß:
Wir sollen einerseits zeigen, dass,
(1) wenn man einen Baum hat und eine Kante so hinzufügen kann, dass dieser Graph eulersch wird, wir einen Kreis bekommen.
Und andererseits, dass,
(2) wenn wir einen Kreis haben, dass wir beim Löschen einer Kante in dem eulerschen Graphen einen Baum bekommen.
Nur wie bitte kann man das zeigen? Könnte man zu (1) vielleicht eine Vollständige Induktion über die Kante E machen? Falls ja, wie läuft sowas ab?
mfg
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:20 Mo 08.12.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
