Networks and Decision

Question 1

What is a spanning tree?

Answer 1

Tree that has all vertices connected

Question 2

What is a tree?

Answer 2

No loops, multiple edges, or cycles, and woll always have one less edge than vertices

Question 3

Answer 3

19km (A-E-G-B-C-H-F-D)

Question 4

Answer 4

Question 5

A- Get Up (1 Minute)
B- Have a shower (5 minutes)Must get up first
C- Get dressed (2 minutes)Must have shower first
D- Boil the kettle(2 minutes) Must get up first
E- Make coffee (1 minute)
F- Enjoy Coffee (5 minutes)Must get dressed and make coffee first
G- Prepare and eat breakfast (10 minutes) Must have coffee first

Make a prerequisite table or an activity chart for the information above;

Answer 5

Question 6

Determine the value of the cuts made on the following diagram (A is source, F is sink):

Answer 6

Cut 1 = 40+50+70=160
Cut 2 = 70+60+40+70=240
Cut 3 = 70+60+80= 210

Question 7

Recall the hungarian algorithm

Answer 7

1. Subtract lowest value in each row from every value in that row
2. If the minimum number of lines to cover all zeroes is equal to allocations, go 6
3. If a column does not contain a zero, subtract lowest value from every value in column
4. If minimum number of lines to cover all zeroes is equal to allocations, go 6

5a. Add the smallest uncovered value to any value covered by two lines, subtract the smallest uncovered from all uncovered values

5b. repeat from step 4

6. Draw a directed bi-partite graph with an edge for every zero value
7. Make allocation and calculate minimum cost

Question 8

Bi-partite graph?

Answer 8

Two groups of vertices that are connected to one or more vertices in the other group

Question 9

What is prims algorithm?

Answer 9

1. Choose random vertex and connect to closest vertex
2. Choose an unconnected vertex that is closes to any connected
3. Repeat step 2 until all vertices are connected to tree