MA010 Graph Theory (an online guide)

Lecture 5: Trees and greedy algorithms


  • Minimum spanning tree (MST) problem
    definition of MST, Kruskal's greedy algorithm (with a proof), Jarník's algorithm (later known as Prim's algorithm), other relations
  • Principles of greedy algorithms
    local "greedy" optimization, a simple job assignment problem with a greedy solution, when greedy solutions do not work optimally
  • Matroids and abstract greedy optimization
    three axioms of independent sets of a matroid, matroid bases, the cycle matroid on the edges of a graph (independent = acyclic), the relation between matroids and an abstract greedy algorithm


This lecture primarily introduces the "greedy" method of discrete optimization - a step-by-step search through local optima which eventually leads (or should lead) to the global optimum. The method is illustrated with greedy algorithms for the Minimum Spanning Tree problem (MST - one of the basic discrete optimization problems), and a simple variant of a job assignment. The abstract greedy algorithm then motivates the introduction of matroids - useful (though rather obscure) discrete structures generalizing graphs. 

[BOOK]Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Study the whole Sections 5.3, 5.4, and 5.5.

Furthermore, have a short look at extensive online resources about greedy algorithms and specifically the MST problem.