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. 

           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}