3

Please help 3(a) and (b), thanks.

For Kruskal's algorithm, the time required to initially sort the edges according to their weights is (m log m), where m := |E| is the number of edges (by using MergeSort or Heap Sort, for example). It can be shown that with an efficient implementation of the vertex-partitioning procedure, that the running time of the entire algorithm is still Om log m). (a) If we have a weighted graph G on n vertices where the degree of each vertex is exactly 6 1, should we use Prim's or Kruskal's algorithm to find an MST? Why? (b) If we have a weighted graph on n vertices where each potential edge is present with probability p= 0.2, independently of all other potential edges, should we use Prim's or Kruskal's algorithm to find an MST? Why