Limited access

Upgrade to access all content for this subject

List Settings
Sort By
Difficulty Filters
Page NaN of 1946

When deciding which edges to include in a minimum spanning tree, you can confirm that an edge belongs to the minimum spanning tree by using the Cut Property.

Which of the following best describes the Cut Property?​

A

If all of a graph's edge costs are distinct from one another and there exists a cycle in the graph, then the cycle's most expensive edge does not belong to any minimum spanning tree of the given graph.

B

If all of a graph's edge costs are distinct from one another and there exists two subsets of nodes in the graph, S and T, where $S\cup T$ contains all of the nodes in the graph but $S\cap T$ is empty, then the least expensive edge that connects S to T does not belong to any minimum spanning tree of the given graph.

C

If all of a graph's edge costs are distinct from one another and there exi​sts a cycle in the graph, then the cycle's most expensive edge belongs to every minimum spanning tree of the given graph.

D

If all of a graph's edge costs are distinct from one another and there exists two subsets of nodes in the graph, S and T, where $S\cup T$ contains all of the nodes in the graph but $S\cap T$ is empty, then the least expensive edge that connects S to T belongs to every minimum spanning tree of the given graph.

Accuracy 0%
Select an assignment template