Assignment 6 due by the end of class Wednesday March 7 2001.
Show that in a union-find data structure which is initialized to a forest of n trees with 1 vertex each, performing m finds and n-1 unions can take Theta(mn) time, whereas performing m finds and n-1 weighted unions takes O(m lgn) time.
o---o o---o---o---o |\ /| |\ /| |\ /| | X | | X | | X | |/ \| |/ \| |/ \| o---o o---o---o---o
Let G be a loopless multigraph with at least three vertices, and let G* be the loopless multigraph obtained by contracting an edge e of G, and removing and resulting loops. Prove that (a) if C is a min cut of G which does not contain e, then C is a min cut in G*, and that (b) if C is the only min cut of G, and C does contain e, then the size of a min cut of G* is greater than the size of a min cut of G.