Written by Min-Koo Seo.

The most important jargon of graph theory are walk, path, circuit, trail, cycle. However there is disparity among discrete mathmatic books and automata books.

I found three definitions :

1) WALK : sequence of vertex which has incident edges.

a) TRAIL : a WALK whose edge is not repeated

PATH : a TRAIL whose vertex is not repeated

b) CIRCUIT : a WALK which strat from and end at the same vertex and whose edge is not repeated.

CYCLE : a CIRCUIT whose vertex is not repeated

2) WALK : same as above

a) PATH : a WALK whose edge is not repeated

simple PATH : a PATH whose vertex is not repeated

b) CYCLE : a WALK which start from and end at the same vertex and whose edge is not repeated

simple CYCLE : a CYCLE whose vertex is not repeated

3)

a) PATH : sequence of edges

simple PATH : a PATH whose edge is not repeated

elementary PATH : a simple PATH whose vertex is not repeated

b) CYCLE : sequence of edges which start from and end at the same vertex

simple CYCLE : a CYCLE whose edge is not repeated

elementary CYCLE : a simple CYCLE whose vertex is not repeated

It is somewhat frustrating that these basic terms are not compatible.

## Post a Comment