T hat eine Tour der Länge von maximal n+1 g.d.w. G einen Hamiltonschen Pfad besitzt.
Sehen wir uns das an einem Beispiel an:
|
|---|
| Alle Kanten aus G aufaddiert ergeben n-1 (4) Einheiten. Dazu kommt noch die Kante, die die Rundreise schließt, mit zwei Einheiten. Das macht zusammen n+1 (6) Einheiten. |
Es könnte aber sein, daß diese schließende Kante im Graphen G schon vorhanden war. In diesem Fall wird lediglich eine Einheit aufaddiert. Insgesamt sind das dann n (5) Einheiten. Deshalb ist nur eine maximale Angeabe korrekt.
|
|
|
|---|
Copyright 1996 by Matthias Hoffmann (TFH Berlin)
letzte Änderung: 1-11-1996