Discrete Mathematics More on Graphs - Discrete Mathematics

How Graphs are coloured?

The procedure by which colour are assigned to each vertex of the graph G in such a manner that same colour is not used for no adjacent vertices is known as Graph colouring. The objective of graph colouring is ti minimize the number of colour used. To colour a graph G, the smallest number of colours required is called its chromatic number. The problem of graph colouring is a NP Complete problem.

What are the steps involved to colour a graph?

The following are steps involved in colouring graph G with n number of vertices:

Step 1 – The vertices of the graph are arranged in some order.

Step 2 – The first vertex is chosen and is coloured with the first colour.

Step 3 – The next vertex is chosen and is coloured with the lowest numbered colour that has not been coloured on any of the adjacent vertices. When all the adjacent vertices are coloured with this colour, a new colour is assigned. Till all the vertices are coloured, this step is repeated.

Example

Graph Colouring

Vertex a is coloured red, the adjacent vertices b and d are coloured with different colour. Then the vertex c is coloured red as no adjacent vertex has the same colour. Hence only 3 colour are used for colouring the complete graph and hence the chromatic number of the graph is 3.

What are the different applications of Graph Colouring?

Graph colouring is used in some of the applications like:

  • Register Allocation
  • Map Colouring
  • Bipartite Graph Checking
  • Mobile Radio Frequency Assignment
  • Making time table, etc.

What is Graph Traversal?

The problem of visiting all the vertices of the graph in a systematic order is known as Graph traversal. A graph can be traversed in two ways:

  • Breadth First Search
  • Depth First Search

Breadth First Search

Breadth First Search (BFS) starts at starting level-0 vertex X of the graph G. Then all the neighbour vertices of X are visited. Once visited, the vertices are marked as “visited” and hence are placed into level-1. Then the same process is started from the level-1 vertices. When every vertex of the graph is being visited, the BFS traversal terminates.

BFS Algorithm

The concept is to visit all the neighbour vertices before visiting the neighbor vertices of neighbor vertices.

  • The status of all the nodes is initialized as “Ready”.
  • The status of the source vertex is changed to “Waiting” and is put in a queue.
  • The following two steps are repeated until the queue is empty:
  1. Remove the first vertex from the queue and mark it as “Visited”.
  2. Add to the rear of queue all neighbors of the removed vertex whose status is “Ready”. Mark their status as “Waiting”.

Problem

For instance, a graph with a source vertex ‘a’ is considered and BFS algorithm is applied to find the traversal order.

BFS Graph

Solution −

  • The status of all the vertices is initialised to “Ready”.
  • The status of a is changed to “Waiting” and kept in queue.
  • Mar a as “visited” and remove from the queue.
  • As neighbour is added to “ready” while b, d and e to end of queue and they are marked as “waiting”.
  • B is marked as “visited” and is removed from the queue. Then neighbour c is at thye end of the queue and mark as “waiting”.
  • Remove d from queue and mark it as “Visited”. It has no neighbor in “Ready” state.
  • Remove e from queue and mark it as “Visited”. It has no neighbor in “Ready” state.
  • Remove c from queue and mark it as “Visited”. It has no neighbor in “Ready” state.
  • Queue is empty and hence stop.

So the traversal order is −

a→b→d→e→ca→b→d→e→c

The alternate orders of traversal are −

a→b→e→d→ca→b→e→d→c

Or, a→d→b→e→ca→d→b→e→c

Or, a→e→b→d→ca→e→b→d→c

Or, a→b→e→d→ca→b→e→d→c

Or, a→d→e→b→ca→d→e→b→c

Application of BFS

  • Identifying the shortest path
  • In case of un-weighted graph, minimum spanning tree.
  • GPS navigation system
  • Detecting cycles in an undirected graph
  • Within one connected component, all the nodes are found.

Complexity Analysis

For instance, consider the G(V,E) graph with |V| number of vertices and |E| number of edges. Every vertex of the graph is visited by BFS algorithm and every edge is checked and the complexity is -

O(|V|+|E|).O(|E|)

It may vary between O(1) and O(|V2|)

Depth First Search

Depth First Search (DFS) algorithm starts from a vertex v, then it traverses to their adjacent vertexes (say x) that has not been visited before and mark as "visited" and goes on with the adjacent vertex of x and so on.

Once all the adjacent vertices are visited, then it backtracks till it finds the first vertex whose adjacent vertex has not been traversed earlier. Then that vertex is traversed and is continued with the adjacent vertices until all the visited vertices are traversed and has no backtrack.

DFS Algorithm

The concept is to visit all the neighbor vertices of a neighbor vertex before visiting the other neighbor vertices.

  • The status of all the nodes is initialized to “Ready”
  • The status of the source vertex is changed to “waiting” and is put in a stack.
  • Until the stack becomes empty, the following two steps are repeated.
  1. Pop the top vertex from the stack and mark it as “Visited”
  2. Push onto the top of the stack all neighbors of the removed vertex whose status is “Ready”. Mark their status as “Waiting”.

Problem

For instance, consider the graph with source vertex a and DFS algorithm is applied for finding the traversal order.

DFS Graph

Solution

  • The status of all the vertices is initialized to “Ready”.
  • The status of a is changed to “waiting” and is put in stack.
  • A is marked as “visited”.
  • Push a’s neighbors in “Ready” state e, d and b to top of stack and mark them as “Waiting”.
  • Pop b from stack, mark it as “Visited”, push its “Ready” neighbor conto stack.
  • Pop c from stack and mark it as “Visited”. It has no “Ready” neighbor.
  • Pop d from stack and mark it as “Visited”. It has no “Ready” neighbor.
  • Pop e from stack and mark it as “Visited”. It has no “Ready” neighbor.
  • Stack is empty. Hence stop.

So the traversal order is −

a→b→c→d→ea→b→c→d→e

The alternate orders of traversal are −

a→e→b→c→da→e→b→c→d

Or, a→b→e→c→da→b→e→c→d

Or, a→d→e→b→ca→d→e→b→c

Or, a→d→c→e→ba→d→c→e→b

Or, a→d→c→b→ea→d→c→b→e

Complexity Analysis

For instance, consider the graph G(V,E) with |V| number of vertices and |E| number of edges. If DFS algorithm visits every vertex in the graph and checks every edge, then the time complexity is −

⊝(|V|+|E|)

Applications

  • Graph cycle is detected
  • Topological sorting is identified
  • Checking a graph to be bipartite
  • Connected components are identified
  • Bridges of the graph are identified
  • Knight’s tour problem is solved
  • Puzzles are solved with only one solution

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Discrete Mathematics Topics