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.
Leave a Reply