Let G = (V, E) be an undirected connected graph and let c : E R + be a function

ID: 3863079 • Letter: L

Question

Let G = (V, E) be an undirected connected graph and let c : E R + be a function specifying the costs of the edges, i.e., every edge has a positive cost. Assume that no two edges have the same cost. Given a set S V , where S contains at least one element and is not equal to V , let eS denote the edge in E defined by applying the cut property to S, i.e., eS = arg minecut(S) ce.

In this definition, the function “arg min” is just like “min” but returns the argument (in this case the edge) that achieves the minimum. Let F be set of all such edges, i.e., F = {eS, S V, S 6= }. In the definition of F, S ranges over all subsets of V other than the empty set and V itself. Answer the following questions, providing proofs for all questions.

1. Consider the graph induced by the set of edges in F, i.e., the graph G0 = (V, F). Is G0 connected?

2. Does G0 contain a cycle?

3. How many edges does F contain?

4. What conclusion can you draw from your answers to the previous statements?

Edit: I'm guessing that the conclusion is that G0 is a minimal spanning tree and we have to prove that it's connected, doesn't have a cycle, and has n - 1 edges?

Explanation / Answer

1) Let G0 is not connected graph.Let there is at least one vertex(A) for which there is no edge. But F is set of all edge which follow aug min function so there must be a path which connects the vertex(A). so it contradicts our assumption. So G0 is connected graph.

2) G = (V,E) is undirected connected graph with different weighted edges. so there must be a minimum spanning tree. S is subset of V and eS follows function argmin. and F is set of such edges. and G0=(V,F) has property of S and eS. if there is cycle in G0 then it will contradict the agrmin property of F. so G0 is acyclic graph.

3) G0 is minimum spanning tree. there is only one path between any two vertexs. a minimum spanning tree has one less edge than number of vertexs. Let no of vertexs is N so numbers of edges are N-1.

4) G0 is subset of graph G. it is not empty graph. it follows the property of argmin function. it has all the property of minimum spanning tree. it is connected it has no cycle. so it is acyclic. and it has n-1 edges.

Navigate

Let G = (V, E) be a weighted undirected, connected graph. Let (u, v) be an edge

Let G = (V, E) be an undirected graph and let w(e) > 0 for edge weights for e G

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Let G = (V, E) be an undirected connected graph and let c : E R + be a function

Question

Explanation / Answer

Related Questions

Navigate