Graph algorithms

After a brief introduction to graphs, this course presents problems on graphs that admit an efficient algorithmic solution. The study of these solutions will provide an opportunity to demonstrate classical properties of graph theory.

Introduction

Example problems
General definitions
Paths and trees


Path problems

A gluttonous solution for the minimal spanning tree
Widthwise paths
The shortest path problem
Depthwise paths


Other problems

The maximum flow problem
The maximum coupling problem

Modules [[m:IF101]] and [[m:IF102]]

I. Introduction - Example problems - General definitions - Paths and trees II. Path problems - A gluttonous solution for the minimal spanning tree - Paths in width - The shortest path problem - Paths in depth III. Other problems - The maximum flow problem - The maximum coupling problem

Printed and online course notes.
Introduction à l'algorithmique, T. Cormen et al, Dunod~(1994).