Suppose that you have a connected, undirected graph G=(V, E) where each edge is colored either...

 

Transcribed Image Text:

Suppose that you have a connected, undirected graph G=(V, E) where each edge is colored either red or blue. Given a number k, you are interested in determining whether there is some spanning tree of G that contains exactly k blue edges. Design a polynomial-time algorithm that finds a spanning tree of G containing the minimum possible number of blue edges. Then: • Describe your algorithm. • Prove that your algorithm finds a spanning tree of G containing the minimum possible number of blue edges. Prove that your algorithm runs in polynomial time. Design an algorithm that finds a spanning tree of G containing the maximum possible number of blue edges. Then: • Describe your algorithm. • Prove that your algorithm finds a spanning tree of G containing the maximum possible number of blue edges. Prove that your algorithm runs in polynomial time. 111. Suppose 7₁ and 72 are spanning trees of G where T₁ contains ki blue edges and T2 contains k2 >k: blue edges. Prove there must be some spanning tree T of G con- taining exactly ki + 1 blue edges. iv. i Design an algorithm that, given a number k, determines whether there is a span- ning tree of G that contains exactly k blue edges. Note that you don't need to find such a spanning tree, you just need to determine whether one exists. Your algorithm should run in time polynomial in n and m (the number of nodes and edges in G), but not in k. Then: Describe your algorithm. • Briefly justify why your algorithm determines whether there is a spanning tree of G containing exactly k blue edges. You don't need to write a formal proof here, but should give a one-paragraph justification as to why your algorithm works. Briefly justify why your algorithm runs in time polynomial in n and m. Suppose that you have a connected, undirected graph G=(V, E) where each edge is colored either red or blue. Given a number k, you are interested in determining whether there is some spanning tree of G that contains exactly k blue edges. Design a polynomial-time algorithm that finds a spanning tree of G containing the minimum possible number of blue edges. Then: • Describe your algorithm. • Prove that your algorithm finds a spanning tree of G containing the minimum possible number of blue edges. Prove that your algorithm runs in polynomial time. Design an algorithm that finds a spanning tree of G containing the maximum possible number of blue edges. Then: • Describe your algorithm. • Prove that your algorithm finds a spanning tree of G containing the maximum possible number of blue edges. Prove that your algorithm runs in polynomial time. 111. Suppose 7₁ and 72 are spanning trees of G where T₁ contains ki blue edges and T2 contains k2 >k: blue edges. Prove there must be some spanning tree T of G con- taining exactly ki + 1 blue edges. iv. i Design an algorithm that, given a number k, determines whether there is a span- ning tree of G that contains exactly k blue edges. Note that you don't need to find such a spanning tree, you just need to determine whether one exists. Your algorithm should run in time polynomial in n and m (the number of nodes and edges in G), but not in k. Then: Describe your algorithm. • Briefly justify why your algorithm determines whether there is a spanning tree of G containing exactly k blue edges. You don't need to write a formal proof here, but should give a one-paragraph justification as to why your algorithm works. Briefly justify why your algorithm runs in time polynomial in n and m.

Answer rating: 100% (QA)

Answer i To find a spanning tree of G containing the minimum possible number of blue edges we can use a modified version of Prims algorithm The algorithm can be described as follows 1 Start with an ar... View the full answer