Toute reproduction sans autorisation du Centre français d’exploitation du droit de copie est strictement interdite. © Techniques de l’Ingénieur, traité Sciences fondamentales AF 205 − 1 Théorie des graphes par Robert CABANE Professeur de mathématiques spéciales au lycée Michel-Montaigne (Bordeaux) Ancien élève de l’École normale supérieure 1. Généralités................................................................................................. AF 205 - 3 1.1 Concepts orientés........................................................................................ — 3 1.2 Concepts non orientés ................................................................................ — 4 1.3 Hypergraphes............................................................................................... — 4 1.4 Suites d’arêtes. Connexité .......................................................................... — 5 2. Modes de représentation....................................................................... — 6 2.1 Listes de succession.................................................................................... — 6 2.2 Matrice d’adjacence..................................................................................... — 7 2.3 Matrice d’incidence ..................................................................................... — 8 3. Nombres et ensembles caractéristiques des graphes................... — 9 3.1 Degrés attachés à un graphe...................................................................... — 9 3.2 Rang et nombre cyclomatique ................................................................... — 9 3.3 Nombre de stabilité interne (externe)........................................................ — 10 3.4 Noyau ........................................................................................................... — 10 3.5 Points et ensembles d’articulation. Nombre de connexité ...................... — 11 3.6 Centres d’un graphe.................................................................................... — 12 3.7 Nombre chromatique.................................................................................. — 12 3.8 Indice chromatique...................................................................................... — 13 3.9 Problème de l’isomorphisme et problèmes NP-difficiles......................... — 14 4. Chemins et circuits ................................................................................. — 14 4.1 Réseaux ........................................................................................................ — 14 4.2 Chemins et circuits eulériens...................................................................... — 15 4.3 Chemins et circuits hamiltoniens............................................................... — 16 4.4 Recherche du plus court chemin................................................................ — 18 4.5 Problème du voyageur de commerce (PVC) ............................................. — 20 4.6 Algorithmes distribués................................................................................ — 21 5. Arbres et arborescences........................................................................ — 21 5.1 Définition des arbres ................................................................................... — 21 5.2 Arbres couvrants sur un graphe................................................................. — 22 5.3 Notion d’arborescence................................................................................ — 26 6. Réseaux de transport.............................................................................. — 26 6.1 Flots dans un réseau de transport.............................................................. — 27 6.2 Méthode de recherche du flot maximal : algorithme de Ford et Fulkerson. — 27 6.3 Problème des flots de coût minimal .......................................................... — 30 7. Graphes bipartis et couplages ............................................................. — 31 7.1 Position du problème et vocabulaire......................................................... — 31 7.2 Problèmes d’affectation .............................................................................. — 32 8. Graphes planaires .................................................................................... — 34 8.1 Généralités ................................................................................................... — 34 8.2 Test de planarité d’un graphe..................................................................... — 35 8.3 Coloriage des graphes planaires................................................................ — 36 9. Implantations d’un graphe dans un autre......................................... — 36 Pour en savoir plus .......................................................................................... Doc. AF 205