91影视

Consider the undirected graph with weighted edges and the subgraphs.The sum of the weights of all the edges in the tree is the spanning-tree cost. The tree with the minimum spanning cost is known as the minimum spanning tree.

(a)

Consider the undirected graph $\mathrm{G}=\left(\mathrm{V},\mathrm{E}\right)$, with more than $\left|\mathrm{V}\right|-1$edges and a unique heaviest edge. The unique heaviest edge cannot be a part of a minimum spanning tree.

Consider the below graph as the counter-example:

In the above diagram, the edge with a weight of 10 is the unique heaviest edge. The minimum spanning tree of the above graph will not accept the heaviest edge since it is not included in the cycle.

Therefore, the provided statement is False, as shown by the counter-example.

(b)

Consider the undirected graph G with the unique heaviest edge e. The graph G has the cycle with a unique heaviest edge as follows:

In the above diagram, the edge D to E is the unique heaviest edge. The edges A, B, C, and D form the cycle. The cycle is the minimum spanning tree of the graph that does not include the unique heaviest edge.

Therefore, the provided statement is True, and the graph proves it.

(c)

Consider the graph G that has the edge e that has minimum weight. Consider the graph given in the diagram below. The edge B to A has a minimum weight of 2.

In the above graph, the minimum spanning tree includes the edge B to the minimum weight edge of the graph.

Therefore, the minimum edge e in a graph must be part of some MST, and the graph diagram proves it.

(d)

Consider the graph G with the lightest unique edge.

The above graph has the lightest unique edge D to E with weight 1. The graph鈥檚 minimum spanning tree will include the edge D to E with weight one since the least minimum weight of the graph is 1.

Therefore, the unique lightest edge of the graph must be part of every true MST that is proved by the graph.

(e)

Consider the graph G with the lightest edge across some cut of G

In the above graph, the minimum edge e of the minimum spanning tree is A to B. The edge D to E is the lightest edge e^' across the cut. The minimum edge e can be replaced by the lightest edge across the cut e^' and obtain a smaller minimum spanning tree.

Therefore, the Lightest edge across some cuts is the part of some MST that is True, which is proved by the graph.

(f)

Consider the graph G with the lightest unique edge.

Consider the above graph that has the lightest unique edge e is B to C. The bold edge with weight 1 is not the part of the MST but the lightest edge in the cycle ABCD.

Therefore, the statement is False, and a counter-example is provided.

(g)

Consider the graph G as follows:

In the above graph, the shortest path from A to D by Dijkstra鈥檚 algorithm is A-D. The edge A-D is the heaviest edge of the graph. Dijkstra鈥檚 algorithms will use the heaviest edge of a cycle; it is on the shortest path from the source to the destination.

Therefore, the provided statement is False, and the counter-example proves it.

(h)

Consider the graph G as follows:

In the above graph, the shortest path between the source and the destination is A-D . The minimum spanning tree of the graph is ABCD. The shortest path between the source and destination is not part of any MST.

Therefore, the provided statement is False, and the counter-example proves it.

(i)

Consider the graph that has negative edges. Prim鈥檚 algorithm always adds the lightest edge between the visited vertices and the unvisited vertices, which is the lightest edge of this cut.

Therefore, Prim鈥檚 algorithm correctly works when there are negative edges.

(j)

Suppose that a graph G contains an r-path from the source to destination but that there is an MST T of G that does not contain an r-path from source to destination. ThenT contains a path from source to destination with an edge e of weight ${\mathrm{w}}_{\mathrm{e}}鈮�\mathrm{r}$ . Consider the partition of vertices made by removing e from T. One vertex e^' of the r-path must be along this cut, as the r-path connects source and destination. Since ${\mathrm{w}}_{{\mathrm{e}}^{\text{'}}}<\mathrm{r}$ , swap e^' for e to get a spanning tree that is lighter than T, a contradiction.