Graphentheorie: Walk vs. Path

Question

Ich bin mit diesem Problem festgefahren. Ich hoffe, jemand wird es besser erklären als alle Erklärungen, über die ich gelesen habe.

Warum kann ein nicht leerer einfacher endlicher Graph keinen Weg maximaler Länge haben, sondern einen Pfad maximaler Länge?

In einem einfachen Diagramm von beispielsweise 4 Eckpunkten: Wenn Sie 50 Mal zwischen 2 Eckpunkten gehen (oszillieren), würde dies die Länge des Spaziergangs 50 Mal verringern. Wäre das nicht länger als jeder Pfad, den Sie möglicherweise aus der Grafik erhalten könnten?

Answer 1

Sie haben verstanden, was tatsächlich passiert, haben aber die Aussage missverstanden, dass ein nicht leerer einfacher endlicher Graph keinen Weg maximaler Länge hat, sondern einen Pfad maximaler Länge haben muss.

Egal wie lange Sie laufen, Sie können immer eine Kante und einen Scheitelpunkt hinzufügen, um einen längeren Spaziergang zu machen. Daher gibt es keine maximale Länge für einen Spaziergang. Ein Pfad kann jedoch einen Scheitelpunkt nicht wiederholen$n$ Eckpunkte im Diagramm, kein Pfad kann länger sein als $n$ Eckpunkte und $n-1$Kanten: Es gibt eine maximal mögliche Länge für einen Pfad. Dies bedeutet, dass der Graph nur endlich viele Pfade enthält, und im Prinzip können wir einfach jeden von ihnen untersuchen und einen längsten finden.