Aufgabe aus der Graphentheorie

Neue Frage »

manuel459 Auf diesen Beitrag antworten »
Aufgabe aus der Graphentheorie
Hey Leute,

ich habe hier folgenden Graphen gegeben: (E5,K5) wobei um das jetzt verständlich zu erklären:

(E1,K1) ist zeichnerisch dargestellt eine Strecke mit 2 Eckpunkten
(E2,K2) ist ein Viereck
(E3,K3) ist ein Würfel in 3D.

also mit Koordinaten (1,1,1) zum Beispiel. Dabei ist wichtig dass nur Kanten zwischen Elementen der Eckenmenge sind, wenn sie sich maximal in einem Eintrag des Tupels unterscheiden.

Betrachten wir nun (E5,K5) und zur eigentlichen Frage:

"Welche Länge kann ein Kreis in diesem Graphen maximal haben?"

Ist keine Hausaufgabe, sondern einfach eine Übung für mich. Wäre sehr froh wenn mich da jemand aufklären kann, habe absolut keine Ahnung.

Danke und LG
Huggy Auf diesen Beitrag antworten »
RE: Aufgabe aus der Graphentheorie
Da sage ich mal. man kann alle Ecken dieses Graphen in einem Hamiltonkreis durchlaufen.
manuel459 Auf diesen Beitrag antworten »
RE: Aufgabe aus der Graphentheorie
wir haben Hamiltonkreise nicht in der Vorlesung gehabt. Gibt es eine andere Begründung?


LG
Huggy Auf diesen Beitrag antworten »
RE: Aufgabe aus der Graphentheorie
Das ist keine Begründung, sondern eine Behauptung. Man kann in der Behauptung das Wort Hamiltonkreis problemlos weglassen. Die Behauptung lautet dann:

Man kann den Graphen (E5,K5) in einem Kreis durchlaufen, der in einer beliebigen Ecke beginnt, alle anderen Ecken genau einmal durchläuft und dann in der Anfangsecke endet. Ein solcher Kreis hat offensichtlich die maximale Länge. Die Behauptung gilt für alle Graphen (En, Kn) mit .

Die Begründung dieser Behauptung liegt in einem Schema, wie man einen solchen Kreis konstruieren kann. Versuche mal, so ein Schema zu finden. Wenn du keinen Erfolg hast, erläutere ich dir gern mein Schema.
Neue Frage »
Antworten »



Verwandte Themen

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