# Three Algorithm True or False Questions

e) Let G = (V,E) be a weighted graph and let T be a minimum spanning tree of G. The path in T between any pair of vertices v_1 and v_2 must be a shortest path in G.

True or False?

f) If an edge e = (u,v) is in a minimum spanning tree of an undirected graph G = (V,e) with nonnegative weight function w, then there exist two vertices x and y in G such that e is on a shortest path from x to y.

True or False?

g) Given a bipartite graph G = (V,E) and a matching M is a set of E, it is possible to determine if M is a maximum matching in G in worst case O(E+V) time.

True or False?

Â© BrainMass Inc. brainmass.com December 24, 2021, 5:58 pm ad1c9bdddfhttps://brainmass.com/computer-science/trees/algorithm-true-false-questions-83389

#### Solution Preview

e) False: A minimum spanning tree is a loop less tree made out of a graph that accounts fro total minimum cost rather than accounting for ...

#### Solution Summary

This solution explains the three algorithm true or false questions in detail.