Théorie des graphes

18h C dont contrôle / 2 crédits ECTS

Anne Germa (Gif)

Un graphe modélise des objets et des relations entre ces objets. Les relations peuvent correspondre à des connexions physiques et le graphe modélise ce qu'on appelle souvent un réseau ; les relations peuvent aussi être conceptuelles (un graphe peut par exemple modéliser un problème de classification sur les objets d'un ensemble, selon certaines relations de préférence, de similarité...). Le cours doit permettre de repérer quelques problèmes que l'on sait résoudre grâce à des propriétés ou des algorithmes portant sur les graphes. Ce repérage a pour objectif de faciliter la délicate opération de modélisation des problèmes qui peuvent se traiter en termes de graphes. On verra aussi que, pour bon nombre de problèmes, on ne connaît pas d'algorithme polynomial de résolution et on donnera pour ces problèmes des méthodes générales (exponentielles) et des méthodes approchées (heuristiques).

Définitions autour des graphes

Graphes non orientés, graphes orientés. Chaînes, cycles, chemins, circuits. Connexité.

Arbre couvrant de poids

Problèmes des plus courts chemins

Cas des longueurs positives : algorithme de Dijkstra. Cas sans circuit : algorithme de Bellman et application à l'ordonnancement. Cas général : algorithme de Dantzig.

Problèmes de flot

Définitions ; flot de valeur maximum et coupe de capacité minimum. Application au couplage maximum dans un graphe biparti. Algorithme de Busacker et Gowen et application à un problème de transport.

Connectivité

Définitions. Théorème de Menger.

Parcours de graphes

Parcours en profondeur, parcours en largeur, application à la recherche des composantes fortement connexes.

Coloration

Définitions et aspects algorithmiques

Méthodes exactes et heuristiques

Problèmes NP - difficiles : exemple du voyageur de commerce. Aperçu sur les méthodes par "séparation et évaluation" et sur quelques classes d'heuristiques : méthodes gloutonnes, méthodes par amélioration itérative, recuit simulé, méthode tabou.