**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:

- Design a polynomial-time algorithm that finds a spanning tree of containing the minimum possible number of blue edges. Then:
- Describe your algorithm.
- 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.

- 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.

- 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.
- 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:
- Describe your algorithm.
- 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:

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

**Multicolored Spanning Trees**