Homework answers / question archive / Let ?? = (??, ??) be a bipartite graph, but this time it is a weighted graph

Let ?? = (??, ??) be a bipartite graph, but this time it is a weighted graph

Computer Science

Share With

Let ?? = (??, ??) be a bipartite graph, but this time it is a weighted graph. The weight of a complete matching is the sum of the weights of its edges. We are interested in finding a minimum-weight complete matching in ??.

 a) Give a legitimate ??? for a branch-and-bound (B&B) algorithm that finds a minimum-weight complete matching in ??, and prove that your ??? is valid. Your ??? cannot be just the cost so far. 

b) Using your ???, apply B&B to find a minimum-weight complete matching in the following weighted bipartite graph ??: ?? = {1,2,3},?? = {4,5,6,7}, ?? = {[(1,4), 3],[(1,5), 4],[(1,7), 15],[(2,4), 1],[(2,5), 8],[(2,6), 3],[(3,4), 3],[(3,5), 9],[(3,6), 5]}. Show the solution tree, the ??? of every tree node generated, and the optimal solution. Also, mark the order in which each node in the solution tree is visited.