My Paper Writer » Essay Blog » Research Paper Help » Multicolored Spanning Trees

# Multicolored Spanning Trees

Multicolored Spanning Trees

## Final Projects: Multicolored Spanning Trees

(70% of the final score)

Description:

Suppose that you have a connected, undirected graph = (,) where each edge is colored either red or blue. Given a number , you are interested in determining whether there is some spanning tree of that contains exactly blue edges. You will:

1. Design a polynomial-time algorithm that finds a spanning tree of containing the minimum possible number of blue edges. Then:
• Implement your algorithm using C/C++/JAVA
• Prove that your algorithm finds a spanning tree of containing the minimum possible number of blue edges.
• Prove that your algorithm runs in polynomial time.
2. Design an algorithm that finds a spanning tree of containing the maximum possible number of blue edges. Then: 1) Describe your algorithm.
• Implement your algorithm using C/C++/JAVA
• Prove that your algorithm finds a spanning tree of containing the maximum possible number of blue edges.
• Prove that your algorithm runs in polynomial time.
3. Suppose ₁ and ₂ are spanning trees of where ₁ contains ₁ blue edges and ₂ contains ₂>₁ blue edges. Prove there must be some spanning tree of containing exactly ₁ + 1 blue edges.
4. Design an algorithm that, given a number , determines whether there is a spanning tree of that contains exactly 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 and (the number of nodes and edges in ), but not in . Then:
• Briefly justify why your algorithm determines whether there is a spanning tree of containing exactly 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 and .

A teamwork project:

Each two or three students form a group, and for each group:

1. Send your name, ID to Ms. Zhengdan Li via email
2. Prepare a report describing how you divide the work, and how you solve the above problems.