[Graphentheorie] hamiltonscher Graph

Neue Frage »

diego09 Auf diesen Beitrag antworten »
[Graphentheorie] hamiltonscher Graph
Hi zusammen,

habe eine Frage zu einer recht simplen Aufgabe, die wie folgt lautet:

Begründen Sie warum ein hamiltonscher Graph ist.

Wenn n=1 ist, also , ist das doch kein hamiltonscher Graph. Er hat zwar einen hamiltonschen Weg, aber keinen Hamiltonschen Kreis. Vollständige Graphen, sind per Definition ja auch erst ab n=3 hamiltonsch.

Hab ich einen Denkfehler oder ist da ein Fehler in der Aufgabe?
HAL 9000 Auf diesen Beitrag antworten »

Als ein in der Graphentheorie nicht sonderlich bewanderter stelle ich mal folgende dumme Frage:

ist eine so feststehende, übliche Bezeichnung für einen bestimmten Graphen, dass man nicht weiter erläutern muss, welcher Graph hinter dieser Bezeichnung steckt?
diego09 Auf diesen Beitrag antworten »

ist ein vollständiger Graph, wobei n die Anzahl der Knoten angibt.
T((lim1+1/t)^t)ddy Auf diesen Beitrag antworten »

Der Vollständigkeit halber(vlt. ist das ja schon nicht mehr relevant für dich)

Da ein Vollständiger Graph mit zwei Knoten u ,v sowohl (u,v) als auch (v,u) als Kanten enthält (in ungerichteten Graphen ist das selbstverständlich) kannst du hierbei von einem Hamelton Kreis von u nach v und zurück ausgehen.

Gerade in ungerichteten Graphen sollte man bei Hameltonkreisen beachten das man durchaus Kanten mehrfach "benutzen" darf. (im Gegensatz zu einem Eulertour bei der das nicht gilt).

(Daher hat der vollständige Graph mit 2 Knoten einen Hameltonkreis aber keine Eulertour.)
Neue Frage »
Antworten »



Verwandte Themen

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