Fachgebiet! Kreis in einen Graphen

Neue Frage »

*Sonnenschein* Auf diesen Beitrag antworten »
Kreis in einen Graphen
Hallo,

wie kann ich zeigen das ein Graph in dem jede Ecke mindestens den Grad zwei hat einen Kreis enthält?

Danke!
mYthos Auf diesen Beitrag antworten »

Das ist aber eine "lustige" Aufgabenstellung. Einen Graphen mit Ecken zweiten Grades, der einen Kreis enthält, den möchte ich erst mal gerne sehen. Hast du ein Beispiel dafür?

mY+
Zizou66 Auf diesen Beitrag antworten »

Die Aufgabe könnte auch einfach nur im Schulmathematikforum schlecht aufgehoben sein. In der Graphentheorie spricht man auch schon mal von solchen Dingen, damit müsste es was zu tun haben. Und bei den passenden Definitionen und Erläuterungen ist dann auch die Aufgabe ernst Augenzwinkern Die sollten dann aber auch gegeben werden *Sonnenschein*...
*Sonnenschein* Auf diesen Beitrag antworten »

Also ich meine das so, dass zum Beispiel ein Viereck (jede Ecke hat den Grad zwei) einen Kreis enthält. (Also das Viereck ist dann der Kreis).

Und jetzt soll ich zeigen das jeder Graph der mindestens an jeder Ecke den Grad zwei hat einen Kreis hat.
mYthos Auf diesen Beitrag antworten »

Ach so, dann hast du die Frage leider im falschen Forum gestellt. Ich verschiebe es mal in den Hochschulbereich.

*** verschoben ***

mY+
*Sonnenschein* Auf diesen Beitrag antworten »

also mein Problem ist das ich nicht weiss wie ich das Allgemein zeigen soll.

Bin ich auf den richtigen weg wenn ich es mit Induktion zeige?

Weil wenn ich zeige das etwas für zwei geht dann kann ich dadurch ja zeigen das es auch für 2+3 ..usw geht oder?

Nur wie ist dann der erste Ansatz bei der Induktion?

Vielleicht bin ich auch auf einen falschen Weg...
 
 
kiste Auf diesen Beitrag antworten »

Du kannst das ganze recht einfach mit einem Algorithmus zeigen. Fange bei einem beliebigen Knoten an und dann immer zu irgendeinem Nachbar. Entweder gehen dir die Knoten aus oder du kommst zu einem Knoten den du schon gesehen hast(->Kreis)
Das kann man vllt. mit Induktion zeigen, muss die Behauptung dann aber dementsprechend gut formulieren
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »