Hamilton Kreis |
| 30.01.2011, 17:08 | Mö | Auf diesen Beitrag antworten » |
| Hamilton Kreis Hey ho, also ich habe zwei Graphen gegeben. Die Frage ist jetzt, welcher der beiden einen Hamilton-Kreis besitzt (Hamilton-Kreis= Kreis der alle Knoten genau einmal durchläuft) Durch einfaches Probieren konnte ich die Aufgabe zwar lösen, jedoch würde mich interessieren ob man vielleicht auch anders auf eine Lösung hätte kommen können. Irgendwo hatte ich mal folgende Formel aufgeschnappt: Graph mit deg(u)+deg(v)>=|V| für beliebige Knoten u,v Element V wobei {u,v} kein Element E, u ungleich v. Meine Ideen: Die Formel sagt also aus das, wenn ich von zwei Beliebigen Knoten den jeweiligen Grad addiere und das Ergebnis größer/gleich als die Anzahl der im Graphen enthaltenen Knoten ist, ist der Graph hamiltonisch? Wobei für die beiden zu wählenden Knoten gelten muss das keine Kante zwischen ihnen existiert. Könnt ich mit dieser Formel wirklich klären ob ein Graph einen Hamiltonkreis enthält oder nich? Gruß mö |
||
| 31.01.2011, 23:22 | Reksilat | Auf diesen Beitrag antworten » |
| RE: Hamilton Kreis http://de.wikipedia.org/wiki/Hamiltonkreisproblem 
Zu Deiner Formel: V={1,2,3,4,5,6} E={{1,3},{1,4},{1,5},{1,6},{2,3},{2,4},{2,5},{2,6}} besitzt keinen Hamiltonkreis. V={1,2,3,4,5} E={{1,3},{1,4},{1,5},{2,3},{2,4},{2,5}} besitzt einen. Beide erfüllen deg(1)+deg(2)>|V| Gruß, Reksilat. |
||
| 01.02.2011, 13:06 | Mö | Auf diesen Beitrag antworten » |
joa danke erstmal für die antwort ^^ hab nochmal woanders nachgefragt zu der von mir angegebenen Formel wäre noch folgendes zu sagen Ist sie erfüllt besitzt der Graph 100% einen Hamiltonkreis gilt sie nicht heißt das aber nicht das der Graph keinen besitzt. Es kann also trotzdem einer vorhanden sein... |
||
| 01.02.2011, 15:46 | Reksilat | Auf diesen Beitrag antworten » |
Und hast Du Dir mein Beispiel (also das erste) angeguckt? Da sollte es ja dann nach Deiner Quelle auch hundertprozentig einen Hamiltonkreis geben. Bei so einem kleinen Graphen müsste der dann auch leicht zu finden sein. Vielleicht bin ich ja einfach nur blind... 
Gruß, Reksilat. |
||
| 03.02.2011, 13:01 | Mö | Auf diesen Beitrag antworten » |
also dein 1. beispiel stimmt natürlich. es gibt keinen Hamilton-Kreis. ich hatte mich bei der defi. meiner Formel etwas unklar ausgedrückt... wir wählen u und v beliebig, was bedeutet es muss für alle knoten gelten das deg(v)+deg(u) größer |V| in deinem Beispiel könnte man Knoten 3 und 4 addieren und würde auf 4 kommen was kleiner ist, als die gesamte Anzahl an Knoten in G. Würde die summe(der Grade von zwei Knoten) aller nicht adjazenten Knoten immer größer gleich der Summe an Knoten von G sein, so würde die Formel hinhauen... |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
