mstshow the result on the equivalence array( show the array as in figure write an algorithm to find maximum cost spanning treethat isthe spanning tree with highest possible cost when can prim' and kruskal' algorithms yield different msts prove thatif the costs for the edges of graph are distinctthen only one mst exists for does either prim' or kruskal' algorithm work if there are negative edge weights consider the collection of edges selected by dijkstra' algorithm as the shortest paths to the graph' vertices from the start vertex do these edges form spanning tree (not necessarily of minimum cost)do these edges form an mstexplain why or why not prove that tree is bipartite graph prove that any tree ( connectedundirected graph with no cyclescan be two-colored ( graph can be two colored if every vertex can be assigned one of two colors such that no adjacent vertices have the same color write an algorithm that determines if an arbitrary undirected graph is bipartite graph if the graph is bipartitethen your algorithm should also identify the vertices as to which of the two partitions each belongs to projects design format for storing graphs in files then implement two functionsone to read graph from file and the other to write graph to file test your functions by implementing complete mst program that reads an undirected graph in from fileconstructs the mstand then writes to second file the graph representing the mst an undirected graph need not explicitly store two separate directed edges to represent single undirected edge an alternative would be to store only single undirected edge (ijto connect vertices and howeverwhat if the user asks for edge (ji)we can solve this problem by consistently storing the edge such that the lesser of and always comes first thusif we have an edge connecting vertices and requests for edge ( and ( both map to ( because looking at the adjacency matrixwe notice that only the lower triangle of the array is used thus we could cut the space required by the adjacency matrix from | | positions to | |(| )/ positions read section on