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. 

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.