img
Question:
Published on: 6 June, 2023

Write short notes on

  • Kruskal’s algorithm for finding MST
  • Graph coloring problem
Answer:

Kruskal’s algorithm for finding MST

minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges. A single graph can have many different spanning trees. Kruskal's algorithm is a minimum-spanning-tree algorithm where the algorithm finds an edge of the least possible weight that connects any two trees in the forest. It is a greedy algorithm n graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.

MST-KRUSKAL(G, w)

{

1.       A ← Ø

2.       for each vertex v ­belongs to V[G]

3.                do MAKE-SET(v)

4.       sort the edges of E into non decreasing order by weight w

5.       for each edge (u, v) ­ E, taken in non decreasing order by weight

6.                do if FIND-SET(u) ≠ FIND-SET(v)

7.                          then A ← A ­ {(u, v)}

8.                                   UNION(u, v)

9.       return A

}

The complexity of the algorithm is as follows:

Sorting of edges takes O(E LogE) time where E is the number of edges.  After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time where V is the no of vertices. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost V2, so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)

 

It is a problem in which we have to color a graph in such a way that no adjacent vertices will have the same color. The minimum number of colors with which we can color a graph is called the chromatic number of the graph.

GCP algo(k)

{

G(V,E ) is a connected graph

g is the adjacency matrix

m=0(chromatic number)

T=list of distinct colors(1,2,……m)

Dead=a Boolean variable

K=next vertex to be colored

1.(i)dead=0

    (ii) repeat while dead=0 through 7

2. (i)x=0

    (ii) repeat while x=0 through step 5

3.(i) T[k]=(T[k+1])mod(m+1)

    (ii) if T[k]=0

          (a)x=1

          (b) return x

4. repeat for j= 1 to n

    (a) if g[k][j]!=0 and T[k]=T[j]

              x=1

             exit

5. if j=n+1

    (a)x=0

    (b)return x

6. if T[k]=0

    (a)dead=0

    (b) return dead

7. if k=n

    (a) repeat for r=1 to n

     Output T[k]

     Else call GCP(k+1)

8. exit

Random questions