Today we will focus on proof. They are not trivial. They are constructive, might be useful in future studies.
Spanning tree of a graph is a tree that contains all the vertices of the graph, and edges of the trees are a subset of edges on the graph, spanning tree is a subgraph of the original graph.
DFS / BFS trees are spanning trees
minimum spanning tree on undirected weighted graph is the spanning tree with minimum sum of weight on edges
Given a weighted undirected graph G, find a spanning tree of graph G such that the sum of weights is minimized
Greedy algorithm
Initialize a tree with a single vertex, chosen arbitrarily from the graph
Grow the tree by one edge: of the eges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
Repeat last step, until all vertices are in the tree.
https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
The solution is not unique. Ties are broken arbitrarily.
Prim’s algorithm 1
Let S = {1}
(*) choose a minimum weighted edge (a,b) from V-S to S, add a to S
repeat (*) until S = V
cost of (*) step added together, note that there are |E| many edges in total, if we use HEAP + linked list, we will add and remove at most 2|E| edges from heap which costs |E| log |V|
Prim’s algorithm 2
Let S = { 1 }
(*) Choose a minimum weighted edge (a, b) from V – S to S, add a to S
Implement by adjacency matrix
repeat (*) until S = V
O(|V|^2)
Claim: each step k of (*)[^1]( Choose a minimum weighted edge (a, b) from V – S to S, add a to S ) , let U_k be the set of edges selected, then there is a MST T T T such taht for all k, U k ⊂ T U_k \subset T Uk⊂T
If the claim is true, then once S = V, the algorithm is correct
Pf by induction:
Obvious when k=0, for any MST it’s true, since no edge
If at step k it is true, and MST = T, such that U_k in T, let’s prove that this is also true for k+1
Case 1: e k + 1 e_{k+1} ek+1 is in T, then we are done.
Case 2: e k + 1 = ( u , v ) e_{k+1} = (u,v) ek+1=(u,v) is not in T, we know u in S, and v in V-S
Then in T, there is a path P from u to v, and let f be the edge in that path P crossing S to V - S. this f is not in U_k (since it’s crossing S to V - S)
then T’ = T - f + (u,v) is another spanning tree (Since P + (u,v) is a cycle, T is connected)
T’ will contain all the U_k, and T’ is a MST (because w(u,v) <= w(f) ) by the prim’s algorithm.
Partition P of a set S is a set of subsets of S, whose union is S
Equivalent Class Finding in a relationship
A equivalent relation R on set S is defined as:
a R b is true (i.e., (a, b) in R)
(symmetric): if (a, b) in R then (b, a) in R
(reflexive): (a, a) in R
(transitive): if (a, b) in R and (b, c) in R then (a, c) in R
Then S can be partitioned into subsets such that within each subset, elements are equivalent to each other (i.e., a R b) and for elements across sets, there is no relationship, each subset is called an equivalent class.
For undirected graph, reachability is a equivalent relationship (a, b) in R means a can reach b in G. Each class is a connected component.
Algorithmic question:
Suppose R is given as a black-box, i.e., you can query the box with input (a, b) and see whether they are in R
what’s the best algorithm / data structure you can use to organize all objects into equivalent classes
UF is a collection of disjoint subsets of a set of objects O
Operations:
Create_new_set(o), create a new subset with o in the set, put this subset in UF
union(o1, o2), do the union of two subsets that o1 and o2 are in, are form a new (sub)set in UF, remove the old subsets
find(o) traverse or return which subset that object o is in
What you can do:
Given 2 objects, check whether they are in the same subset
Implementation:
Reversed tree, each object node is pointing to another object node, except one taht is pointing to a virtual root for indexingarray implementation: index = object key, A[index] = parent, parent = -1 means rootReduce complexity:
Union by rank
Path Compression
Create a set S containing all edges in the graph
Create F as disjoint subsets of vertices, initialized to be F = {{1}, {2}, {3}…} disjoint single set of vertices
Create T = empty set as storage for the final spanning tree
while S is non empty, and F is not yet of size 1
Remove an edge with minimum weight from Sif the removed edge connects two different elements (subsets of V) in F then combine two sets in F to be oneThe edge is added to the spanning tree TS is implemented by heap, so the total push/pop time is O(|E| log |V|)
F is union-find set, total O (|E|log |V|)
Pf for connectness:
By contradiction:
Let T ∗ T* T∗ be a minimum spanning tree W ( T ∗ ) < W ( T ) W(T*) < W(T) W(T∗)<W(T). Let e ∗ e* e∗ be an edge in T ∗ − T T* - T T∗−T such that its weight is minimum in T T T *.
So adding $ e* $ into $ T$, will create a cycle C
