Discrete Structure (Graph Theory | Walk, Path, Trial, Cycle and Circuit)
Graph Theory |Walk, Path, Trial, Cycle and Circuit in Graph|
Walk
Let G=(V, E) a Graph, then
A walk in G is a list W={u, e1, v1, e2, v2 ...... v} whose elements are alternatively vertices and degrees.
The vertices u and v are called its end-vertices.
The vertices v1, ........ are called inner vertices.
In a simple graph, walk can be denoted by sequence of vertices only.
Path
Let G=(V, E) be a Graph, then
A path in G is a walk with no repeated vertex and edges.
Trial
Let G=(V, E) be a Graph, then
A trial in G is a walk with no repeated edges.
Cycle
Let G=(V, E) be a Graph, then
A cycle in G is a closed path.
In a cycle, start and end vertex are same.
Circuit
Let G=(V, E) be a graph, then
A trial in G is a walk with no repeated edges. Now a closed trial in G is closed circuit.
Example: In the graph given below, construct walk, path, trial, cycle and circuit from a to e.
Solution Here,
1. Walk (Vertex and Edge can be repeated)
1. Walk (Vertex and Edge can be repeated)
walk = {a, b, f, a, b, e}
2. Path (Vertex and Edge is not repeated)
path = {a, b, f, e}
3. Trial (Vertex can be repeated, Edges not repeated)
trial = {a, b, f, g, a, f, e}
4. Cycle (Vertex not repeated, Edge not repeated, close path)
cycle = {a, b, e, f, a}
5. Circuit (Vertex can be repeated, edge not repeated, close trial)
circuit = {a, f, b, e, f, g, a}