Course Content
Chapter I. Basic definitions
1. "Intuitive" definition of a graph
2. Mathematical definition of a graph
3. Order, orientation and multiplicity
3.1. Order
3.2. Orientation
3.3. Multiplicity
4. Relations between the elements of a graph
4.1 Relations between vertices
4.2 Relations between arcs and vertices
4.3 Graph qualifiers
5. Matrices associated with a graph
5.1 Vertex-arc incidence matrix
5.2 Adjacency matrix or vertex-vertex incidence matrix
5.3 Condensed form of sparse matrices
6. Vocabulary related to connected graph
6.1 Chain, path, length
6.2 Connected graph
6.3 Cycle and circuit
6.4 Cocycle and Cocircuit.
Chapter II. Cycles
1. Cyclomatic and cocyclomatic numbers
1.1 Decomposition of cycles and cocycles into elementary sums
1.2 Arc Colouring Lemma (Minty 1960)
1.3 Cycle basis and cocycle basis
2. Planarity
2.1 Planar Graph
2.2 Euler's formula
2.3 Kuratowski's theorem (1930)
2.4 Dual graph
3. Tree, forest and arborescence
3.1 Definitions
3.2 Properties
3.3 Maximum (or spanning) tree
Chapter III. Flow problems
1. Definitions
2. Search for a maximum flow in a transport network
2.1 Definition
2.2 Ford-Fulkerson theorem
2.3 Ford-Fulkerson algorithm
3. Search for a compatible flow
Chapter IV. Pathway problems
1. Search for connected components
1.1 Presentation of objectives
1.2 Trémeaux-Tarjan algorithm
2. Finding the shortest path
2.1 Presentation of the conditions
2.2 Moore-Dijkstra algorithm
3. Search for a spanning tree of maximum weight in a graph
3.1 Presentation of objectives
3.2 Kruskal Algorithm (1956)
Chapter V. Hamiltonian and Eulerian Problems
1. Hamiltonian Problem
1.1 Definitions
1.2 Necessary condition for the existence of a Hamiltonian cycle
1.3 Sufficient condition for the existence of a Hamiltonian circuit
1.4 Sufficient condition for the existence of a Hamiltonian cycle
2. Eulerian Problem
2.1 Definitions
2.2 Necessary and sufficient condition for the existence of an Eulerian chain
2.3 Local algorithm to construct an Eulerian cycle
2.4. Relation between Eulerian and Hamiltonian problem
Chapter VI. Colouring
1. Definitions
2. Vertex colouring
3. Arc colouring
4. Proposals
5. The "4 colours" theorem
6. Perfect graph