Aufgabe aus der Graphentheorie |
28.08.2017, 18:04 | manuel459 | Auf diesen Beitrag antworten » |
Aufgabe aus der Graphentheorie 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 |
||
28.08.2017, 20:20 | Huggy | Auf diesen Beitrag antworten » |
RE: Aufgabe aus der Graphentheorie Da sage ich mal. man kann alle Ecken dieses Graphen in einem Hamiltonkreis durchlaufen. |
||
30.08.2017, 13:12 | 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 |
||
30.08.2017, 13:31 | 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. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|