You can find lecture notes here.
The following slides have been done for a oneweek school on Graph Theory and Optimization at University of Oulu, Finland, September 1518th, 2015
 0) Why is it useful?
Objectives of this school

learn how to model problems (from various domains) using graphs

know the available tools to handle these problem

classical algorithms

Linear Programming

decide if a problem is ``easy" or ``difficult"

know what to do when facing a ``difficult" problem
 exact exponential algorithms
 parameterized algorithms
 approximation algorithms
 heuristics

1) Introduction to Graphs
Many definitions to be remembered
 graph, vertex/vertices, edge
 neighbor, degree
 path, cycle
 connected graph
 tree
 subgraph, spanning subgraph

2) Weighted Graphs: Shortest Paths and Spanning Trees
 weighted graph, distances
 Deciding connectivity
 Shortest path tree in undirected graph O(E), (BFS)
 Computing Shortest path tree, (E + V log V) (Dijkstra)
 Computing Min. spanning tree O(E log E), (Kruskal)
Exercises

3) Flow: FordFulkerson Algorithm
 flow, cut
 FordFulkerson algorithm, O(E flowMax) for rational capacities
 Min Cut = Max Flow
 Menger Theorem (max number disjoint paths = min size of separator)
 Matching (Hungarian method, Edmonds algorithm, Hall Theorem)
Exercises

4) Computational Complexity (in brief)
 P, NP, NPhard, NPcomplete
 3SAT, Hamiltonian path, Coloring, Vertex Cover, ...
 Approximation algorithm

5) Introduction to Linear Programming
 linear programme.
 graphical method of resolution.
 Linear programs can be solved efficiently (polynomialtime).
 Integer programs are a lot harder (in general no known polynomial algorithms)
In this case, we look for approximate solutions.
Exercises

6) Introduction to Duality in LP
 How to compute a Dual Programme.
 Weak/Strong duality Theorem.
 Optimality certificate (Complementary Slackness).
Exercises

6.5) Model Graph Problems with LP
 Revisit graph problems (flow, shortest path, cuts, matching...) with LP
Exercises
 7) Integer Linear Programming
 ILP allow to model many problems
 there may be a huge integrality gap
(between OPT(LP) and OPT(ILP)).

if no integrality gap (e.g., totally unimodular matrices),
then Fractional Relaxation gives Optimal Integral Solution

concrete example: RWA in WDM networks

8) Approximation Algorithms
 Minimum Vertex Cover vs. Maximum Matching
 Fractional relaxation is a method to obtain for some problems (Vertex Cover, Set Cover):
 Lower bounds on the optimal solution of an integer linear program (minimization).
 Polynomial approximation algorithms (with rounding).

9) Parameterized Algorithms
 Parameterized Problem: input (size n) + parameter k
 FPT algorithm: in time f(k) n^{O(1)}
 Kernelization: Data reduction
 Kernelization <=> FPT
 Linear Kernel for Vertex Cover