geschlossener Weg gleich Kreis?

21.12.2010, 09:51	Maria86	Auf diesen Beitrag antworten »
geschlossener Weg gleich Kreis? Meine Frage: Ein geschlossener Weg ist ein Weg der im selben Knoten beginnt und endet. Zeigen Sie: Wenn ein Graph einen geschlossenen Weg enthält, der keine Kante doppelt geht, so enthält er auch einen Kreis. Meine Ideen: Ich hab erstmal die Definition von einem Weg und einem Kreis aufgeschrieben. Def: Kreis, falls nur Start- und Endknoten von W identisch sind, das heißt falls v1 = vn und so weiter... Def Weg ie Menge {vi,vi + 1} ist Element von E, falls G ein ungerichteter Graph ohne Mehrfachkanten ist. Es klingt ja eigentlich recht trivial und auch logisch das nach der Aufgabenstellung ein Weg bzw dieser beschriebene Weg ein Kreis sein muss. Nur finde ich da keinen wirklich guten Ansatz das zu zeigen bzw zu beweisen.
21.12.2010, 10:17	wisili	Auf diesen Beitrag antworten »
RE: geschlossener Weg gleich Kreis? Beim Kreis müssen die Knoten (bis auf den ersten und letzten) paarweise verschieden sein, beim Weg nicht.
21.12.2010, 11:43	Maria86	Auf diesen Beitrag antworten »
Die Einschränkung besagt ja das keine Kante doppelt gegangen wird. Somit gilt dann ja auch beim Weg das die Knoten paarweise verschieden sein müssen. Und bei beiden sind nun auch Start und Endknoten gleich. zB der Graph: a-->b b-->c c-->d d-->e d--->b Wäre ja ein geschlossener Weg und ein Kreis. Und die Knoten sind paarweise verschieden.
21.12.2010, 11:53	wisili	Auf diesen Beitrag antworten »
Was ist beim Knoten c im geschlossenen Weg a-b-c-d-e-c-a ?
21.12.2010, 13:23	Maria86	Auf diesen Beitrag antworten »
Der Knoten c wird mehrfach durchlaufen, aber keine Kante wird mehrfach durchlaufen. Sind sozusagen 2 "Kreise" entstanden. Bei einem ungerichteten Graph müssen also mind 3 Kanten und 3 Knoten existieren die alle miteinander verbunden sind um einen Kreis zu erhalten. Knoten c hat in diesem Fall 4 ausgehende Kanten also Grad von 4, die anderen vom Grad 2.
21.12.2010, 14:18	wisili	Auf diesen Beitrag antworten »
Der Weg a-b-c-d-e-c-a enthält offensichtlich den Kreis a-b-c-a. Er entsteht aus dem Weg durch «Abkürzen», d.h. Auslassen des Kreises -c-d-e-c- (von c zu c).
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »