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

  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.
  3. Submit your report

Multicolored Spanning Trees

Last Updated on February 10, 2019 by EssayPro