May 10, 2019 , , ,

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. 

           A)   
Graph
Solution Here, 
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}