Théorie des graphes

Compétences requises

Algorithmes et structure de données

--

Prerequisites of this lecture are algorithms and data structure.

Compétences visées

Ce module a pour but l’acquisition des savoirs fondamentaux en théorie des graphes, et notamment, au travers d’exemples pris en réseaux et en algorithmie distribuée, de montrer la flexibilité de ce modèle.

Les notions fondamentales d’algorithmes pour les graphes doivent permettre aux étudiants de comprendre de nombreux problèmes en réseau, et de connaître leur résolution via des algorithmes de graphes classiques. 

Choisir le type de graphe le plus adéquat pour modéliser un problème rencontré. 

Comprendre les différentes métriques permettant de caractériser un graphe.

Connaître les algorithmes classiques en théorie des graphes;

Appliquer un algorithme efficace de recherche de plus court chemin.

--

This lecture aims to promote the acquisition of fundamental notions in graph theory, particularly through a few illustrations picked in distributed algorithms and network infrastructures.

Through the different classic graph algorithms, the students will be able to understand the most common problems in networking, and to know the most accurate resolution, exploiting well-known algorithms.  

Select the most accurate graph to model a given problem;

Understand the different metrics which characterize a graph;

Know the most fundamental algorithms in graph theory;

Select and apply an efficient algorithm to find a shortest path.

Syllabus

Le cours abordera les notions suivantes :

Graphes non-orientés et orientés 

Arbres, forêts, arbres couvrant minimum

Graphes spécifiques (ex : graphe planaire) et leurs propriétés.

Notions élémentaires de graphes : coupes, connexité, ensembles indépendants.

Algorithmes de plus courts chemins (Dijkstra, Bellman-Ford).

Flot dans les réseaux.

Problème de coloration de graphes

--

The lecture will comprise:

Oriented Graphs & Multigraphs.

Trees, Spanning-Forests, MST, Steiner trees.

Specific Graphs (e.g. planar graphs) and their properties;

Basic notions in graph theory: cut, separator, connexity, independent sets.

Shortest paths algorithms (Dijkstra, Bellman-Ford, A*).

Multicommodity flow problem in data networks.

Graph coloring for resource allocation.

Contact