Euler-Graphen (Beweis, unzusammenhängende Graphen?!) |
15.08.2012, 13:09 | dNa | Auf diesen Beitrag antworten » |
Euler-Graphen (Beweis, unzusammenhängende Graphen?!) Moin Bin grad beim Thema Euler-Graphen dran und hab einige Fragen: A) Kann es auch unzusammenhängende Euler-Graphen geben? B) Beweis vom Satz: "Ist G ein Euler-Graph, so ist jede Ecke von G gerade". Hoffe mir kann jemand bei den Fragen helfen Meine Ideen: zu A) Die Definition einer Euler-Rundtour bedeutet doch, dass sie eine geschlossene Euler-Tour ist, die alle Kanten des Graphen enthält und keine Kante doppelt ist. zB ein Graph mit einer isolierten Ecke (deg = 0) und einer Ecke mit einer Schlinge (deg = 2). Alle Ecken sind gerade und eine Euler-Tour wäre ja eigentlich nur die Schlinge. zu B) Bew: v ist eine beliebige Ecke von G. v ? E(G) 1. Fall: v ist isoliert. deg (v) = 0 => v ist gerade. 2. Fall: v ist nicht isoliert. a) Alle zu v inzidenten Kanten sind Schlingen => v ist gerade b) v hat mind. eine inzidente Kante, die keine Schlinge ist. => deg (v) ist eine gerade Zahl. So stehts in meinem Skript und wirklich weiter komme ich nicht |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|