Question

As you can see, there are 12 blank squares that denote distances between each of the eight nodes (that is, the boxes with letters in them). Use each of the following numbers to create your own model, then solve it using the minimal spanning tree technique:

2

5

6

11

3

3

7

7

7

4

6

9

Step 1 (10% of grade): Place each the numbers (above) in one of the blank squares. There is no rhyme or reason to it: just place them. You should have no numbers left over and no empty squares.

Step 2 (40%): Use the minimal spanning tree technique (covered in your handout and in your notes) to find the smallest sum that allows you to connect all of your nodes (the squares with the letters in them).  

Step 3: (30%) What paths did you choose? List them for me.

Step 4: (20%) What is the sum of your solution? Tell me. VIP: It is NOT 70 (that is the value of all 12 numbers, and is not the solution).

il 44%9:28 AM 2015-07-28 REP...del v3 blanks V2 - Read-only Read Only - You can't save changes to t... Numbers for the graph: 2 5 6 11 3 3 7 7 7 4 6 9 B C H G a .

Thank you for the help!

Answer 1

Step 1

Let us place the numbers as shown below

N 00 6 A C 11 5 3 D 3 7 E 7 7 F 6 H 4 9 G

Step 2

An approach to get the minimum spanning tree of a graph is -

• first remove all edges from the graph
• place all the edges on a priority queue arranged by their weight (lowest weights first)
• deque each edge from the queue and add it to the graph only if the edge's end points are not connected. Otherwise skip the edge.

So in our case, queue would contain edges as below

[ AB(2), BE(3), CE(3), FG(4), AD(5), BC(6), FH(6), DE(7), EF(7), EH(7), GH(9), BD(11) ]

After dequeing each edge and adding to the graph / skipping, we see the minimum spanning tree as below

2 B A C 5 3 D 3 E 7 F 6 H 4 G

Step 3

Edges that are in our minimum spanning tree are -

AB, AD, BE, CE, EF, FG, FH.

Step 4

Smallest Sum = 2 + 5 + 3 + 3 + 7 + 4 + 6 = 30