Théories des graphes

Objectifs de l’enseignement :

Les théories des graphes sont devenues un fondement théorique et pratique incontournable dans le processus de modélisation de certains problèmes dans plusieurs domaines. L’apport des graphes dans la résolution des problèmes réside dans la simplicité graphique, la similitude avec des aspects distribués et les notions de parcours et de recherches de chemins. L’objectif de ce cours est de présenter à l’étudiant d’une part un de modélisation de solution sous forme de graphe, d’autre part ce cours contiendra un ensemble de techniques permettant à l’étudiant de résoudre ses problèmes à travers des algorithmes comme la recherche de chemin minimal, le flot maximal etc.

Connaissances préalables recommandées Contenu de la matière :

Chapitre I. Définitions de base

I.1. Définition « intuitive » d’un graphe

2. Définition mathématique d’un graphe
3. Ordre, orientation et multiplicité
   • Ordre
   • Orientation
   • Multiplicité
4. Relations entre les éléments d’un graphe

• Relations entre sommets
• Relations entre arcs et sommets
• Qualificatifs des graphes

5. Matrices associées à un graphe

• Matrice d’incidence sommet-arc
• Matrice d’adjacence ou d’incidence sommets-sommets
• Forme condensée des matrices creuses

6. Vocabulaire lié à la connexité

• Chaîne, chemin, longueur
• Connexité
• Cycle et circuit
• Cocycle et

Chapitre II. Cycles

1. Nombres cyclomatique et cocyclomatique
   1. Décomposition des cycles et des cocycles en sommes élémentaires
   2. Lemme des arcs colorés (Minty 1960)
   3. Base de cycles et base de cocycles

2. Planarité

1. Graphe Planaire
2. Formule d’Euler
3. Théorème de Kuratowski (1930)
4. Graphe Dual

3. Arbre, forêt et arborescence
   1. Définitions
   2. Propriétés
   3. Arbre maximal (ou couvrant).

Chapitre III. Flots

1. Définitions
2. Recherche d’un flot maximum dans un réseau de transport
   4. Définition

5. Théorème de Ford-Fulkerson
6. Algorithme de Ford-Fulkerson

3. Recherche d’un flot compatible

Chapitre IV. Problèmes de cheminement

1. Recherche des composantes connexes
   1. Présentation des objectifs
   2. Algorithme de Trémeaux-Tarjan
2. Recherche du plus court chemin
   1. Présentation des conditions
   2. Algorithme de Moore-Dijkstra
   3. Recherche d’un arbre de poids extrémum
      1. Présentation des objectifs
      2. Algorithme de Kruskal 1956

Chapitre V. Problèmes Hamiltonien et Eulérien

1. Problème Hamiltonien
   1. Définitions
   2. Condition nécessaire d’existence d’un cycle hamiltonien
   3. Condition suffisante d’existence d’un circuit hamiltonien
   4. Condition suffisante d’existence d’un cycle hamiltonien
2. Problème Eulérien
   1. Définitions
   2. Condition nécessaire et suffisante d’existence d’une chaîne eulérienne
   3. Algorithme local pour tracer un cycle eulérien
   4. Lien entre problème eulérien et hamiltonien

Chapitre VI. Coloration

1. Définitions
2. Coloration des sommets
3. Coloration des arêtes
4. Propositions
5. Le théorème des « 4 couleurs »
6. Graphe parfait

Mode d’évaluation : Examen (60%) , contrôle continu (40%)

Références

• Claude Berge, Graphes et hypergraphes, Bordas 1973, (300 pages).
• Nguyen Huy Xuong, Mathématiques discrètes et informatique, Masson, 1997
• Aimé Sache, La théorie des graphes, Que-Sais-Je ?, 1974 ; réédition prévue en 2004 chez
• Kaufmann, Des points des flèches, la théorie des graphes, Dunod, Sciencespoche, épuisé.
• Alan Gibbons, Algorithmic graph theory, Cambridge University Press, 1985
• Reinhard Diestel, Graph Theory, Second Edition, Springer-Verlag,
• Bojan Mohar, Carsten Thomassen, Graphs on surfaces, John Hopkins University Press, Baltimore, 2001.