3
$\begingroup$

English is not my mother tongue so I don´t know exactly wich is the difference between a tour and path in graphs theory context. I think that in both cases it is a way throught various vertex or points. Is this correct?

$\endgroup$
4
  • $\begingroup$ Usually, a path connects two vertices without repeat. A tour goes though all vertices. $\endgroup$
    – Ed Pegg
    Aug 22, 2017 at 14:53
  • $\begingroup$ So the difference is if vertices are repeated? $\endgroup$
    – Ixer
    Aug 22, 2017 at 15:10
  • 2
    $\begingroup$ All vertices -- tour. Some vertices -- path. Neither repeats a vertex. $\endgroup$
    – Ed Pegg
    Aug 22, 2017 at 15:11
  • $\begingroup$ Seems that a tour is a clycle according to this phrase in wikipedia :"A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once (except for the vertex that is both the start and end, which is visited twice)." Is this incorrect in wikipedia? $\endgroup$
    – Ixer
    Aug 22, 2017 at 15:40

2 Answers 2

9
$\begingroup$

Walk - A sequence of vertices and edges, where the edges connect the adjacent vertices in the sequence

Tour - a walk with no repeated edges

Path - a walk with no repeated vertices

Source: CS 70 MT1 Review Spring 2018 @ UC Berkeley

$\endgroup$
1
  • $\begingroup$ can you link to the cs70 review? $\endgroup$
    – John D
    Sep 7, 2020 at 22:55
1
$\begingroup$

A path is a walk with no repeated vertices.

A trail is a walk with no repeated edges.

A tour is a walk that visits every vertex returning to its starting vertex. A tour could visit some vertices more than once. If you visit them exactly once, then the tour is a Hamiltonian cycle.

A cycle is a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .