Graphen und NetzwerkeSalesman

In einem Graphen mit 8 Städten muss jeder Hamiltonkreis auch 8 Städte enthalten. Somit gilt:

• Es gibt 8 Auswahlmöglichkeiten für die 1. Stadt.
• Nachdem die erste Stadt ausgewählt wurde, gibt es nur noch 7 Auswahlmöglichkeiten für die 2. Stadt.
• Danach gibt es 6 Auswahlmöglichkeiten für die 3. Stadt.
• Weiter geht's mit 5 Auswahlmöglichkeiten für die 4. Stadt.
• Dann gibt es noch 4 Auswahlmöglichkeiten für die 5. Stadt.
• …
• Schließlich bleibt für die 8. Stadt nur noch 1 Wahl übrig.

Dies bedeutet, dass es insgesamt 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40 320 mögliche Pfade gibt. Eine Kurzschreibweise für dieses Produkt ist 8! oder Faktor 8.

Du kannst dir vorstellen, dass es unter Umständen nicht möglich ist, direkt zwischen zwei Städten zu reisen, ohne dabei über eine andere Stadt zu fahren. In diesem Fall haben wir es mit keinem vollständigen Graphen mehr zu tun, und es wird viel schwieriger, die Anzahl der Hamiltonkreise zu finden, falls es überhaupt welche gibt.