Given an undirected graph G=(V, E) with weights and a vertex , we ask for a...

Given an undirected graph G=(V, E) with weights and a vertex , we ask for a minimum weight spanning tree in G where is not a leaf (a leaf node has degree one). Can you solve this problem in polynomial time? Please write the proof.

Solutions

Expert Solution

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.A single graph can have many different spanning trees • They all must have the same number of edges, but if it is a weighted graph, they may differ in the total weight of their edges • Of all spanning trees in a weighted graph, one with the least total weight is a minimum spanning tree (MST) • It can be useful to find a minimum spanning tree for a graph: this is the least-cost version of the graph that is still connected, i.e. that has a path between every pair of vertices

Finding a minimum spanning tree: Prim’s algorithm • As you know, minimum weight paths from a start vertex can be found using Djikstra’s algorithm • At each stage, Djikstra’s algorithm extends the best path from the start vertex (priority queue ordered by total path cost) by adding edges to it • To build a minimum spanning tree, you can modify Djikstra’s algorithm slightly to get Prim’s algorithm • At each stage, Prim’s algorithm adds the edge that has the least cost from any vertex in the spanning tree being built so far (priority queue ordered by single edge cost) • Like Djikstra’s algorithm, Prim’s algorithm has worst-case time cost O(|E| log |V|) • We will look at another algorithm: Kruskal’s algorithm, which also is a simple greedy algorithm • Kruskal’s has the same big-O worst case time cost as Prim’s, but in practice it can be made to run faster than Prim’s, if efficient supporting data structures are used

venereology answered 11 months ago

Next > < Previous

Related Solutions

Prove or disprove: If G = (V; E) is an undirected graph where every vertex has...

Prove or disprove: If G = (V; E) is an undirected graph where every vertex has degree at least 4 and u is in V , then there are at least 64 distinct paths in G that start at u.

You are given an undirected graph G = ( V, E ) in which the edge...

You are given an undirected graph G = ( V, E ) in which the edge weights are highly restricted. In particular, each edge has a positive integer weight from 1 to W, where W is a constant (independent of the number of edges or vertices). Show that it is possible to compute the single-source shortest paths in such a graph in O(E+V) time.

Consider an unweighted, undirected graph G = <V, E>. The neighbourhood of a node v ∈...

Consider an unweighted, undirected graph G = <V, E>. The neighbourhood of a node v ∈ V in the graph is the set of all nodes that are adjacent (or directly connected) to v. Subsequently, we can define the neighbourhood degree of the node v as the sum of the degrees of all its neighbours (those nodes that are directly connects to v). (a) Design an algorithm that returns a list containing the neighbourhood degree for each node v ∈...

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each...

Given an undirected graph G = (V,E), consisting of n vertices and m edges, with each edge labeled from the set {0,1}. Describe and analyze the worst-case time complexity of an efficient algorithm to find any cycle consisting of edges whose labels alternate 0,1.

Design a linear-time algorithm which, given an undirected graph G and a particular edge e in...

Design a linear-time algorithm which, given an undirected graph G and a particular edge e in it, determines whether G has a cycle containing e. Your algorithm should also return the length (number of edges) of the shortest cycle containing e, if one exists. Just give the algorithm, no proofs are necessary. Hint: you can use BFS to solve this.

5. Suppose we are given both an undirected graph G with weighted edges and a minimum...

5. Suppose we are given both an undirected graph G with weighted edges and a minimum spanning tree T of G . (a) Describe an algorithm to update the minimum spanning tree when the weight of a single edge e is decreased. (b) Describe an algorithm to update the minimum spanning tree when the weight of a single edge e is increased. In both cases, the input to your algorithm is the edge e and its new weight; your algorithms...

Determine, for a given graph G =V,E and a positive integer m ≤ |V |, whether...

Determine, for a given graph G =V,E and a positive integer m ≤ |V |, whether G contains a clique of size m or more. (A clique of size k in a graph is its complete subgraph of k vertices.) Determine, for a given graph G = V,E and a positive integer m ≤ |V |, whether there is a vertex cover of size m or less for G. (A vertex cover of size k for a graph G =...

In a simple undirected graph H the sum of vertex degrees is 60. What is the...

In a simple undirected graph H the sum of vertex degrees is 60. What is the smallest possible number of vertices in this graph? What is the largest possible number of vertices in the graph?

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3...

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph. a) Draw a maximal plane graphs on six vertices. b) Show that a maximal plane graph on n points has 3n − 6 edges and 2n − 4 faces. c) A triangulation of an n-gon is a plane graph whose infinite face boundary is a convex n-gon...

Let G = (V, E) be a directed graph, with source s ∈ V, sink t...

Let G = (V, E) be a directed graph, with source s ∈ V, sink t ∈ V, and nonnegative edge capacities {ce}. Give a polynomial-time algorithm to decide whether G has a unique minimum s-t cut (i.e., an s-t of capacity strictly less than that of all other s-t cuts).

Subjects