COSC 511		FALL 2014

HW 1009.txt    Due 10/16

1. An undirected graph is given in matrix form

    a | b | c | d
    ==|===|===|===
a | 0 | 7 | 4 | 5
b | 7 | 0 | L | 6
c | 4 | L | 0 | 3
d | 5 | 6 | 3 | 0

where L means there is no edge (weight = Large)

What will be the cost of the MST?




2. Consider this undirected graph with vertex set {a, b, c, d, e}

    a | b | c | d | e
    ==|===|===|===|===
a | 0 | 1 | 8 | 1 | 4
b | 1 | 0 | 12| 4 | 9
c | 8 | 12| 0 | 7 | 3
d | 1 | 4 | 7 | 0 | 2
e | 4 | 9 | 3 | 2 | 0


What is the cost of an MST?



3.  Consider again the graph in #2. What are all the MSTs?




4. Consider again the graph in #2. What are the minimum paths for

A. (a, c)

B. (a, e)

C. (b, c) 




5. Consider again the graph in #2.

What is the minimum cost of a spanning tree such that vertex a is a leaf 
node in the spanning tree?  (Notice, the spanning tree is not a required to be
a *minimum* spanning over the graph -- the requirement is that it is a tree 
with a as a leaf).

A. 7
B. 8
C. 9
D. 10




6. Consider an undirected graph of n nodes. The adjacency matrix is n X n
where the diagonal elements are 0 and the non-diagonal elements are 1.
Which of the follow statement is true (only one is true)?

A. The graph has no MST.
B. The graph has a unique MST of cost  n-1.
C. The graph has multiple distinct MSTs, each MST has cost  n-1.
D. The graph has multiple distinct MSTs, each MST has a different cost.




7. Consider a graph with n nodes, labelled 1 through n.  You obtain a MST 
starting at root vertex 1.  
From the same initial graph, you obtain all the shortest paths from vertex 1 to
vertex n. 

Is the path from 1 to n in the MST a shortest path from 1 to n in the original
graph?

A.  YES

B.  NO




8. Consider all MSTs from a graph G. Are all shortest paths from vertex i to vertex
j (i != j) guaranteed to be present in some MST of G?

A. YES
B. NO