CS410, Summer 1998
Quiz #15
August 6

Consult no sources.				Name:

[The quiz in class had the graphs hand-drawn with dots and lines.]

1. Find a minimum spanning tree for the graph below.

Edge	Weight
--------------
(1,2)   2
(1,3)   2
(1,4)   5
(1,8)   2
(2,3)   3
(3,4)   4
(3,7)   3
(3,8)   3
(4,5)   3
(4,6)   4
(4,7)   2
(6,7)   5
(6,8)   7
(7,8)   3

2. Find (shortest path) distance from s to every other vertex for the
graph below.

Edge    Weight
--------------
(s,c)	1
(s,g)	5
(a,s)	2
(b,e)	2
(c,a)	2
(c,b)	2
(c,d)	2
(c,g)	3
(d,b)	1
(d,e)	4
(f,s)	3

ANSWERS
=======

1 had a few possible answers.  The minimum weight is 21.

2 vertex   distance
  a		3
  b		3
  c		1
  d		3
  e		5
  f		infinity
  g		4