Eulerscher Graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es sei G = (V, E) ein zusammenhängender ungerichteter einfacher Graph mit |V(G)| [mm] \ge [/mm] 3.
Zu zeigen: G Eulersch [mm] \gdw [/mm] jede Kante von G liegt auf einer ungeraden Anzahl von Kreisen |
//Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.//
Hallo!
Meine Überlegung bei dieser Aufgabe ist, dass man hier die folgende Aussage nutzen kann:
G Eulersch [mm] \gdw [/mm] G ist eine Vereinigung von kantendisjunkten Kreisen.
Davon komme ich jetzt aber nicht auf die ungerade Anzahl von Kreisen. Brauche einen Schubs in die richtige Richtung an dieser Stelle.
Vielen Dank.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:24 Mi 31.10.2012 | | Autor: | Stoecki |
> Es sei G = (V, E) ein zusammenhängender ungerichteter
> einfacher Graph mit |V(G)| [mm]\ge[/mm] 3.
> Zu zeigen: G Eulersch [mm]\gdw[/mm] jede Kante von G liegt auf
> einer ungeraden Anzahl von Kreisen
> //Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.//
>
> Hallo!
>
> Meine Überlegung bei dieser Aufgabe ist, dass man hier die
> folgende Aussage nutzen kann:
>
> G Eulersch [mm]\gdw[/mm] G ist eine Vereinigung von kantendisjunkten
> Kreisen.
>
> Davon komme ich jetzt aber nicht auf die ungerade Anzahl
> von Kreisen. Brauche einen Schubs in die richtige Richtung
> an dieser Stelle.
>
> Vielen Dank.
hast du denn schon eine der beiden richtungen wenigstens zeigen können?
die hinrichtung sollte eigentlich ziemlich einfach mit kontraposition gehen.
versuch den teil mal und schreib noch mal, wenn du nicht weiter kommst.
für die rückrichtung würde ich mir überlegen, was denn passiert, wenn ein kreis durchlaufen wurde. dieser darf kein weiteres mal durchlaufen werden, also würde ich versuchen die invariante zu beweisen, dass der graph, der entsteht, wenn man diesen kreis entfernt immernoch diese eigenschaft besitzt (oder leer ist). daraus würde die behauptung folgen
hoffe das hilft erstmal
gruß bernhard
|
|
|
|
