Gerichtete Kreise im Digraph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei G ein stark zusammenhängender Digraph, dessen zu Grunde liegender ungerichteter Graph mindestens einen Kreis ungerader Länge enthält.
Zeige das G auch mindestens einen (gerichteten) Kreis ungerader Länge enthält.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. |
Hallo Leute.
Ja die oben stehende Aufgabe beschäftigt mich nun schon eine Weile, ohne das ich das gefühl habe nahe an einer Lösung dran zu sein.
Zu zeigen das G einen Kreis enthält ist trivial, da G stark zusammenhängend ist.
Bleibt zu zeigen das min. ein Kreis ungerade Länge hat.
Meine Idee war es den Kreis (im ungerichteten Sinne) zu nehmen. Dieser hat ungerade viele Kanten. Je nachdem wierum ich nun den Kreis ablaufe, habe ich eine ungerade Anzahl an Kanten die in Laufrichtung liegen und eine gerade Anzahl an Kanten die entgegen der Laufrichtung liegen.
Dann probierte Ich einen Kreis ungerader Länge zu konstruieren.
Dazu nehme ich also die Menge mit ungerade Anzahl an gleichorientierten Kanten. Für die Kanten (x,y) die entgegen der Laufrichtung lagen füge ich einen x-y-Pfad ein, den es nach Aufgabenstellung geben muss.
Im folgenden konnte ich dann auch zeigen das immer ein ungerader Kreis existiert. Allerdings fiel mir dann auf, das meine Annahme, das die Kanten des Kreises in eine ungerade und eine gerade Menge gleichorientierter Kanten zerfällt falsch war. Es kann durch kanten-paare (x,y) und (y,x) auch vorkommen das beide Mengen gerade sind. Mein Beweis ging dadurch nicht mehr auf.
Weiß jemand rat? Lässt sich mein Ansatz irgendwie retten?
Oder muss man da komplett anders ran gehen?
Ich bin ratlos...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Fr 09.11.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
