MA010 Graph Theory (an online guide)

# Lecture 5: Trees and greedy algorithms

Outline

• 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

Goals

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.

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.