Solutions to Assignment 5
or as three separate files:soltns5a.pdf
If you have trouble viewing in the browser, download to your
desktop and try viewing from there.
For each vertex v in the graph:
Do a DFS (or BFS) from v and let S be
the set of all vertices marked
For each w in S which is different from
v, add the edge vw to the transitive closure
This problem is a bit tricky if the graph has cycles. Let us
assume that it does not.
First compute the transitive closure. Then:
For every vertex u
For every vertex v not equal to u
For every vertex w
not equal to u or v
If uv, vw and uw are edges, delete uw
Note: this may not always give the one with the minimum number
of edges if the graph has a cycle.
Consider the case of a graph with three vertices and all 6
One transitive reduction has edges: 12, 23, 31
Another one has edges: 12,21,13,31
Union by weight
The reason is essentially the same as that given in the last two
paragraphs of Section 16.1 of the notes.
A find operation takes at most the maximum depth of any of the
trees. Initially all trees have zero depth.
The only way a tree can increase its depth is when two trees are
The leader of the smaller tree has its weight at least double
for each merge, since it gains all of the nodes
of the larger tree as children.
Since no tree has more than n nodes, a node can double its
weight at most log_2 (n) times so the maximum depth of
any tree is at most log_2 (n).