PDA

View Full Version : Bezüglich offene bzw geschlossene Euler Linie

bubum
30-09-2002, 14:38
Hab folgende Frage im PO gefunden:

Was versteht man unter einer offenen bzw geschlossenen Eulerschen Linie, was unter einer offenen bzw geschlossenen Hamiltonschen Linie? Sei G ein schwach zusammenhängender Graph. Wie kann man dann mit Hilfe der Knotengrade feststellen, ob G eine offene Eulersche Linie ist?

Ich dachte eigentlich eine Eulersche Linie muss geschlossen sein!?
Überhaupt die ganze Frage ist mir ein wenig suspekt!

Wäre super wenn mir jemand das erklären könnte!

mfg
Neo
30-09-2002, 15:25
könnte vielleicht eine Fangfrage sein, da die Definition eindeutig von einem geschlossenen Kantenzug spricht. Gäbe es einen offenen Kantenzug, gäbe es mindestens einen Knoten mit ungeradem Grad (nämlich 1), wodurch die Charakteristik der Eulerschen Graphen nicht mehr zutrifft.
RAUSCHfrei
30-09-2002, 17:33
Vielleicht hats früher im Mathe3-Skriptum mal diesen Unterschied gegeben, aber in unserem Skriptum ist immer nur von geschlossenen Kantenzügen bzw. Kreisen die Rede!
heder
30-09-2002, 17:59
IHMO ist es so, in einer offenen Eulerschen Linie gibt es 2 Knoten
ungeraden Grads (nicht notwendigerweise 1), also den Anfang und das Ende.


O-----O-----O hat eine "offene" eulersche Linie

+-A-----B-+ hat auch eine "offene" eulersche Linie
| | | | obowhl beide ungerade Grad haben
| +-----+ | startet in A nach B, zurück nach A und
+---------+ über die 3 Kante wieder nach B



hth

Hannes
Snigo
30-09-2002, 18:20
Laut folgender Seite http://fachschaft.informatik.fh-muenchen.de/~ms/2d/mathe/m1_kap5/m1_kap5.htm gilt:

Definition:
Durchläuft in einem Grapgen G ein offener oder geschlossener Kantenzug Z alle Kanten von G, so heißt z eine offene oder geschlossene Euler'sche Linie von G.

Satz:
Ein ungerichteter zusammenhängender Graph G besitzt dann und nur dann eine offene (geschlossene) Euler'sche Linie, wenn es in G zwei (keine) Knoten von ungeradem Grad gibt.

Da bei der Definition eines Eulerschen Graphen im Skript nicht die Rede von einer offenen Linie ist und das auch sonst nirgends erwähnt, glaube ich nicht dass die PO Frage kommen kann.

Außer er hat es halt extra in der Vorlesung einmal erwähnt - weiß das vielleicht jemand?

mfg

snigo
AntiBit
30-09-2002, 23:08
Wie auch immer, es ist ja nicht schwer zu merken:

Wenn genau 2 Knoten ungeraden Grad haben, so gibt es eine offene eul. Linie. Bei nur geraden Graden ist es eine geschlossene.

Offene Eulerlinie ist nichts anderes als eine geschlossene Eulerlinie, aber Startknoten != Zielknoten (deswegen ja offen, siehe offene Kantenfolge)

Zusammenhängende Graphen die eine offene eulersche Linie besitzen sind NICHT Eulersch. Nur wenn sie eine geschlossene besitzen.
patricasso
03-10-2002, 16:10
Die genauen Definitionen von "offenen Eulerlinien" etc. gibts übrigens (erstaunlicherweiße leicht verständlich) im grauen Mahte Büchlein vom Baron - Band 3.
heder
03-10-2002, 19:22
Bei Quellenangaben, bitte auch die Seite angeben (ev. auch Auflage), das
ersparrt allen anderen das Rumblättern.
patricasso
04-10-2002, 22:34
Prüfung ist zwar vorbei, aber zum vorigen Post.

Hab das Buch leider nicht zur Hand gehabt, und konnte so die genaue Seite nicht angeben.
Ich wollts nur kurz erwähnen.

Selbstverständlich werd ich das nächste Mal auch Seitenzahlen nennen. Hoff man hat es trotzdem gefunden.
Sorry, falls es eventuelle Umstände bereiten haben sollte (wollt nur helfen).
heder
07-10-2002, 09:35
nix für ungut, ist nur a Hinweis für die Zukunft.