An undirected weighted graph G is given below Figure 16: An undirected weighted graph has 6 vertices, a through f, and 9 edges. Vertex d is on the left. Vertex f is above and to the right of vertex d. Vertex e is below and to the right of vertex f, but above vertex d. Vertex c is below and to the right of vertex e. Vertex a is above vertex e and to the right of vertex c. Vertex b is below and to the right of vertex a, but above vertex c. The edges between the vertices and their weight are as follows: d and f, 1; d and e, 4; f and e, 2; e and a, 2; f and a, 3; e and c, 5; c and a, 7; c and b, 5; and a and b, 6. (a) What is the minimum weight spanning tree for the weighted graph subject to the condition that edge {d, e} is in the spanning tree? (b) How would you generalize this idea? Suppose you are given a graph G and a particular edge {u, v} in the graph. How would you alter Prim’s algorithm to find the minimum spanning tree subject to the condition that {u, v} is in the tree?
An undirected weighted graph G is given below
Figure 16: An undirected weighted graph has 6 vertices, a through f, and 9 edges. Vertex d is on the left. Vertex f is above and to the right of vertex d. Vertex e is below and to the right of vertex f, but above vertex d. Vertex c is below and to the right of vertex e. Vertex a is above vertex e and to the right of vertex c. Vertex b is below and to the right of vertex a, but above vertex c. The edges between the vertices and their weight are as follows: d and f, 1; d and e, 4; f and e, 2; e and a, 2; f and a, 3; e and c, 5; c and a, 7; c and b, 5; and a and b, 6.
(a) What is the minimum weight spanning tree for the weighted graph subject to the condition that edge {d, e} is in the spanning tree?
(b) How would you generalize this idea? Suppose you are given a graph G and a particular edge {u, v} in the graph. How would you alter Prim’s
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 6 images
- Recommended textbooks for youDatabase System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSONDatabase System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag…Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education