Beschreibung
Ein verallgemeinerter Petersengraph P(n,k) ist genau dann
hamiltonsch, wenn er einen Kreis enthält, der alle Knoten
des Graphen genau einmal beinhaltet. Die Anwendungen von
Untersuchungen hierzu sind mannigfaltig, eine hiervon ist
das altbekannte Problem des reisenden Handelsmannes. Hier
wird nun für k=4 eine neue Methode entwickelt, die es
gestattet, mit Hilfe relationentheoretischer,
graphentheoretischer, zahlentheoretischer und
kombinatorischer Hilfsmittel die Hamiltonizität von P(n,k)
für jedes n größer 4 zu beweisen. Ansatzpunkt ist die Idee,
dass jeder Hamiltonkreis zu einem verallgemeinerten
Petersengraphen aus einem oder mehreren Strukturelementen
bestehen muss. Beispielsweise könnte man sich eine Halskette
vorstellen, die aus verschiedenen Fragmenten zusammengesetzt
ist. Die vorgestellte Methode gestattet es, nicht nur zu
einer gegebenen Durchlaufungsfolge festzustellen, ob sie
einen Hamiltonkreis induziert, sondern die Menge aller
verschiedenen Hamiltonkreise in P(n,k) für ein vorzugebendes
n zu bestimmen.
Dr. habil. Reinhard Rauscher, Professor für
betriebliche Informatik und Mathematik, Hochschule
Osnabrück, Fakultät MKT, Institut für Management und
Technik.
