Let A, B, C, D be the vertices of a square with side length 100. If we want to create a minimum-weight spanning tree to connect these four vertices, clearly this spanning tree would have total weight 300 (e.g. we can connect AB, BC, and CD). But what if we are able to add extra vertices inside the square, and use these additional vertices in constructing our spanning tree? Would the minimum-weight spanning tree have total weight less than 300? And if so, where should these additional vertices be placed to minimize the total weight? Let G be a graph with the vertices A, B, C, D, and possibly one or more additional vertices that can be placed anywhere you want on the (two-dimensional) plane containing the four vertices of the square. Determine the smallest total weight for the minimum-weight spanning tree of G. Round your answer to the nearest integer.
Let A, B, C, D be the vertices of a square with side length 100.
If we want to create a minimum-weight spanning tree to connect these four vertices, clearly this spanning tree would have total weight 300 (e.g. we can connect AB, BC, and CD).
But what if we are able to add extra vertices inside the square, and use these additional vertices in constructing our spanning tree?
Would the minimum-weight spanning tree have total weight less than 300? And if so, where should these additional vertices be placed to minimize the total weight?
Let G be a graph with the vertices A, B, C, D, and possibly one or more additional vertices that can be placed anywhere you want on the (two-dimensional) plane containing the four vertices of the square.
Determine the smallest total weight for the minimum-weight spanning tree of G. Round your answer to the nearest integer.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
