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
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.
Note: I encourage you to add n additional points (for n=1, 2, 3) to your graph and see if you can figure out where these point(s) need to be located to minimize the total weight of the spanning tree. You are welcome to use Excel or write a computer program to help you calculate the location of these additional point(s) that will minimize the total weight of the spanning tree.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
