Walk

• A walk is a finite alternating sequence v₁e₁v₂e₂v₃e₃...e_nv_n of vertices and edges, beginning and ending with same or different vertices.
• Here both edges and vertices can be repeated.

Some terminologies

1. Length of the walk: The number of edges is called length of the walk.
2. Closed & open walk: A walk is said to be closed if its origin & terminous vertex (v0 = vn) is equal otherwise it is called open walk.

Trail

• Trail is same as walk but here vertices can be repeated but edges cannot.
• For above graph a trail can be : a - e2 - b - e9 - g - e10 - c - e12 - d - e5 - g - e11 - e

Circuit

• A closed trail is called circuit.

Path

• A walk is called path if all vertices are not repeated.

Cycle

• A closed path is called cycle.

Eulerian path

• A path in a graph is said to be an Eulerian path if it traverses each edge in the graph once and only once.

Eulerian circuit

• A circuit in a graph is said to be an Eulerian circuit if it traverses each edge in the graph once & only once.

Eulerian ciruit : l - e15 - k - e14 - j - e11 - i - e10 - h - e8 - g - e7 - f - e5 - e - e4 - d - e3 - c - e2 - b - e1 - a - e16 - l - e13 - j - e12 - h - e9 - f - e6 - d - e18 - b - e17 - l.

Eulerian graph

• A connected graph which contain an Eulerian circuit is called Eulerian graph.

Hamiltonian Path

• A path which contain every vertex of a graph G exactly once is called Hamiltonian graph.

Hamiltonian circuit

• A circuit that passes through each of the vertices in a graph G exactly once except the starting vertex & end vertex is called Hamiltonian circuit.

Hamiltonian Graph

• A connected graph which contain Hamiltonial circuit is called Hamiltonian graph.

1. Determine a minimum Hamiltonian circuit for the graph given below.

Sol: As every vertex should be covered so - ( a 2 d 5 e 6 c 4 b 1 a ) will be minimum Hamiltonian circuit

2. Draw a graph with six vertices containing a Hamiltonian circuit but not Eulerian Circuit.

Sol:

We can traverse all the vertex but can't traverse all edge without repeating some edge.

3. Discuss the diagram shown below

(i) Draw Hamiltonian circuit and Hamiltonian path.
(ii) Is it Hamiltonian graph?
(iii) Is it Euler Graph?

Dijkstra Algorithm

• This algorithms for single source shortest path problem.
• If a weighted graph is given then we have to find shortest path from some starting vertex to all other vertices.
• As we have to find the shortest path so it is a minimization problem or optimization problem.
• So optimization problem should be solved using greedy method.
• So Dijkstra algorithm gives a procedure for getting a optimal solution that is minimum result (shortest path).

Shorted path in weighted graph

• We use Dijkstra's algorithm to find shortest path.

And shorted path will be - a b c e d f

Question ↓

Chromatic number

• The least number of color required for coloring of a graph G is called chromatic number.
• Note:
  • The chromatic number of graph G is denoted by 𝒳(G).
  • If 𝒳(G) = K, then the graph is called k-chromatic.
  • If the graph is complete then chromatic number = number of vertex.
  • Chromatic number of null graph is 1.
  • If a graph is circuit with n vertices then
    (i) It is 2-chromatic if n is even
    (ii) It is 3-chromatic if n is odd

Q- Determine the chromatic number of graph below

Sol:

• This graph have odd number of vertex so this will be 3-chromatic.
  

The Welsh Powell Algorithm

• Video lecture ⇗
• This algorithm is used to find the proper colouring of a graph, hence to find chromatic number of a graph.
• Algorithm:
  1. Find the degrees of all vertices.
  2. Arrange the vertices according to decreasing order of their degree.
  3. Assign colour 1 to the first vertex in the list and move forward in the list, find a vertex non adjacent to previous vertex and colour it with colour 1. Keep on moving in the list to find non adjacent vertices to the vertices having colour 1 and assign them colour 1.
  4. Repeat the step 3 for colouring previously non coloured vertices using colour 2. And repeat the process of colouring using 3, 4, and more colours until all the vertices are coloured.

Example: Find the chromatic number of the following graph using Powell's algorithm.