MA010 Tutorial 2
Fr´ed´eric Dupuis
This tutorial covers material from lectures 1 and 2.
Problem 1
Consider the following weighted graph:
‚ ‚
‚ ‚
‚ ‚
‚a
b c
d
e
f g
1
1
3
3
1
3
4
1
2
(a) Simulate a depth-first search starting at vertex a and looking at adjacent vertices
clockwise starting at noon. Draw the resulting search tree.
(b) Simulate a breadth-first search starting at vertex a and looking at adjacent vertices
clockwise starting at noon. Draw the resulting search tree.
(c) Find a minimum spanning tree by simulating Jarn´ık’s algorithm starting at vertex
a and looking at adjacent vertices clockwise starting at noon. Draw the resulting
tree.
Problem 2
Let G be a weighted undirected graph, and let T be a minimum spanning tree of G.
Suppose that we now create the graph G1 from G by increasing the weights of all the
edges by some value x.
(a) Is T still a minimum spanning tree in G1? Prove it, or find a counterexample.
(b) Is every shortest path between two vertices in G still the shortest path in G1? Prove
it, or find a counterexample.
Source: http://www.cs.umd.edu/class/spring2002/cmsc451/hw2.ps
1
Problem 3
Show that all minimum spanning trees must have the same multiset of weights.
Source: http://www.eecis.udel.edu/˜saunders/courses/621/03f/hwQ.html
Problem 4
(a) Show that in each k-connected graph, each set of k vertices belongs to a common
cycle.
(b) For every k, find a k-connected graph with a set of k ` 1 vertices that do not belong
to a common cycle.
Source: http://kam.mff.cuni.cz/˜jelinek/kag2_z0708/hw2.pdf
Problem 5
Given a directed graph G and a spanning tree T of G, a forward edge is an edge not in T
that goes from a vertex to one of its descendents in T (it “bypasses” T). Show that if T is
a BFS search tree, there are no forward edges.
2