offene Euler-Touren < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:14 Mi 01.02.2006 | | Autor: | dump_0 |
Hallo.
Ich soll notwendige & hinreichende Bedingungen für offene Euler-Touren (also Euler-Touren bei denen Anfangs- und Endknoten verschieden sind) finden und beweisen das diese auch gelten müssen.
Ich habe mir bereits folgendes überlegt:
notwendig: [tex]n \ge 2[/tex], mind 1 Knoten muss ungeraden Knotengrad haben
hinreichend: (n ungerade), |E| [mm] \le [/mm] |V| - 1
Ich weiß nicht ob das reicht, was aber wichtiger ist, wie sollte ich das am besten beweisen ?
Würde mich über Hilfe freuen :)
Mfg
[mm] dump_0
[/mm]
|
|
| |
|
Hallo und guten Morgen,
eine offene Euler-Tour ist ja eine Tour, die jede Kante genau einmal enthaelt und so,
dass Anfangs- und Endpunkt der Tour verschieden sind.
Die Tour l'auft in jeden Knoten, der nicht Anfangs- und Endpunkt ist, genauso oft hinein wie hinaus, d.h. man kommt auf den Verdacht, dass gilt:
G hat offene Euler-Tour genau dann, wenn G zush. ist und genau zwei Knoten von G ungeraden Grad haben.
[mm] ''\Rightarrow'' [/mm] hab ich Dir gerade begruendet, und [mm] ''\Leftarrow'' [/mm] kannst Du ja mal selber versuchen.
Viele Gruesse,
Mathias
|
|
|
|
