Euler Digraph, hilfe |
| 19.07.2009, 23:56 | biber111 | Auf diesen Beitrag antworten » |
| Euler Digraph, hilfe habe eine Aussage die ich beweisen möchte, da ich denke dass sie in der Klausur drankommt. Habe schon 2 Versuche unternommen. 2 verschiedene Methoden. Könnt ihr mir hierzu feedback geben obs sauber ist? ZZ: Digraph eulersch genau dann wenn deg_in=deg_out "->" Klar, denn wenn ein Graph eulersch ist, darf er jede Kante genau einmal durchlaufen, d.h für jede Kante die in einen Knoten reingeht muss auch genau eine wieder rausgehen. Also gilt deg_in=deg_out. "<-" Wähle einen längstmöglichen Eulerkreis in Abhängigkeit von n. IA: n=2 Sei (v_1, v_2 , v_1) mein längster Kreis wobei für beide Knoten deG_in=deg_out=1 gilt. IV Graph G mit abs(V)=n ist eulersch wenn deg_in=deg_out für alle v \el\ V IS von n-> n+1 Sei nun (v_1 , v_n , v_(n+1), v_1) mein längster Kreis. Nach Vorraussetzung wissen wir, dass v1 bis v_(n+1)den gleichen Eingangs / ausgangsgrad haben. Also existieren Paare von Kanten (v_i , v_(n+1)) und (v_(n+1) , v_(i+1)) Gegeben sei nun ein Graph mit n+1 Knoten. Den n+1 Knoten und alle seine inzidenten Kanten lassen wir weg. Nach IV ist der Restgraph nun eulersch Nun fügen wir v_(n+1) und seine beiden Kanten hinzu und löschen die Verbindung (v_i , v_(i+1)). Folglich hat sich an den Eingangs / Ausgangsgraden nix geändert und der Graph bleibt eulersch. Da mir der erste Beweis nicht gerade gut gefällt, weil der IS nicht sauber ist(und ich nicht weiss was ich besser machen soll) - hier Plan b. "->" klar "<-" Wir bauen uns ein Eulerkreis T. Sei T leer und Graph mind 2Knoten. Wähle beliebigen Knoten Xx. Da G zusammehängend muss es einen nachfolger von x geben y. Verbinde xy mit einem Boden. DA deg_in (y) = deg_out (y) muss es einen Bogen yz geben, startend von y. So fahren wir beliebig fort und wegen degin=degout kann dieser Prozess nur terminieren, wenn der letzte Bogen, den wir in T einfügen in x hineingeht, also eine Kreisschließende Kante ist. Falls ihr nen Link habt wo der Beweis korrekt aufgeschrieben wird, wäre ich euch auch seeeeehr dankbar. Also vielen Dank schonmal, Grüße |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
