Basic terms of Graph

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.

Similar Posts:

Your email is never published nor shared.