How to do these 3 questions Thank you so much 1 Prove that t

How to do these 3 questions? Thank you so much

1. Prove that the red rule for Algorithm Greedy-MST works correctly.

2. Use Algorithm Greedy-MST to derive an algorithm for the minimum spanning tree problem. Your algorithm should be different from ones discussed in class.

3. You plan to drive from city A to city B along a highway and you have a map showing distances between gas stations on your route. Your car’s gas tank, when full, holds enough gas to travel k kilometers. You wish to make as few gas stops as possible along the way. Give an efficient algorithm to determine at which gas stations to stop and prove that your algorithm gives you an optimal solution

Solution

A connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees. A minimum spanning tree (MST)or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.

A minimum spanning tree has (V – 1) edges where V is the number of vertices in the given graph.

Sort all the edges in non-decreasing order of their weight.

Pick the smallest edge. Check if it forms a cycle with the spanning tree

formed so far. If cycle is not formed, include this edge. Else, discard it.

Repeat step#2 until there are (V-1) edges in the spanning tree.