Week 11

In this penultimate week of classes, we discussed some of the important algorithms in graph theory. In particular, we discussed we turned our attention to two questions regarding weighted graphs (recall that a weighted graph is simply an edge-colored graph whose colors are positive integers.
  1. how can we find a spanning tree whose total weight has minimal value?
  2. (MST)
  3. How can we find the path with shortest total weight between two vertices?
  4. (SDP)
We began by discussing the two algorithms that solve the (MST) problem first. To understand how these work, we'll think of MST in terms of
MST=minimal+connected+acyclic+spanning
The first algorithm, named after J. Kruskal intuitively adds the edge minimal edge that is legal at each step:
(Kruskal)
  1. Let \(T\) be the graph without edges and \(V(T)=V\)
  2. if \(T\) is not connected, add an edge \(e\) in \(E\) that reduces the number of components of minimal weight
  3. reallocate \(T=T\cup \{e\} \)
  4. repeat step 2
Note that by Konig's theorem the number of components reduces if and only if the edge does not lie on a cycle in \(T\). We could thus reinterpret Kruskal's algorithm