Algorithms: Acceptable answers in pseudocode or Python
Consider a connected, undirected, weighted graph G = (V, E, w), along with a single given hub node v EV. A hub node is a vertex which has high degree, e.g., deg(v) > VI/2. In general, an MST of G may contain an arbitrary number of edges which are incident to v. Instead, we want to find a minimum hub-independent spanning tree, defined as a spanning tree which uses at most two edges incident to v, and has weight less than or equal the weight of all other such spanning trees. Give an algorithm that solves this problem in O(E lg V + V2) time. (1 point) Note that for some input graph G and hub vertex v, it may be impossible to construct a spanning tree using only two edges incident to v. Give an example of such a graph and hub vertex. (1 point) Give an example of a graph G and hub vertex v for which the spanning tree described above exists and is not an MST. Identify the minimum hub-independent spanning tree and an MST. (1 point) Let K5 be the complete graph on 5 vertices and v be a fixed vertex. Assign weights to this graph such that any minimum hub-independent spanning tree has exactly two edges incident on v. (5 points) Write pseudocode for an algorithm which takes a graph G and a hub vertex v and computes a minimum hub-independent spanning tree. Comment your code. If no such tree exists, your algorithm should return null. (3 points) Prove the correctness of your algorithm using the cycle and cut properties of an MST. Consider a connected, undirected, weighted graph G = (V, E, w), along with a single given hub node v EV. A hub node is a vertex which has high degree, e.g., deg(v) > VI/2. In general, an MST of G may contain an arbitrary number of edges which are incident to v. Instead, we want to find a minimum hub-independent spanning tree, defined as a spanning tree which uses at most two edges incident to v, and has weight less than or equal the weight of all other such spanning trees. Give an algorithm that solves this problem in O(E lg V + V2) time. (1 point) Note that for some input graph G and hub vertex v, it may be impossible to construct a spanning tree using only two edges incident to v. Give an example of such a graph and hub vertex. (1 point) Give an example of a graph G and hub vertex v for which the spanning tree described above exists and is not an MST. Identify the minimum hub-independent spanning tree and an MST. (1 point) Let K5 be the complete graph on 5 vertices and v be a fixed vertex. Assign weights to this graph such that any minimum hub-independent spanning tree has exactly two edges incident on v. (5 points) Write pseudocode for an algorithm which takes a graph G and a hub vertex v and computes a minimum hub-independent spanning tree. Comment your code. If no such tree exists, your algorithm should return null. (3 points) Prove the correctness of your algorithm using the cycle and cut properties of an MST
