Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Stéphane Pelle poste 3159 15 mai 2002 Cours conçu au sein de l'Équipe Formats d

Stéphane Pelle poste 3159 15 mai 2002 Cours conçu au sein de l'Équipe Formats d'Échange du Service de la Documentation Géographique L La a T Th hé éo or ri ie e d de es s G Gr ra ap ph he es s. . ( (c co ou ur rs s I IT T1 1 2 20 00 02 2) ). . b e f c d g h a 1 2 3 4 5 6 7 8 9 La Théorie des Graphes, cours IT1 2002 IGN/ENSG/CPRI/SP page n° 2/65 IDENTIFICATION Commanditaire : École Nationale des Sciences Géographiques Réalisé à l'Institut Géographique National 2/4, avenue Pasteur 94 165 Saint-Mandé Cedex Auteur : Stéphane Pelle (poste 3159 ou 3161). École Nationale des Sciences Géographiques, Cellule Pédagogique et de Recherche en Informatique Anciennement au Service de la Documentation Géographique Exploitation du Serveur Général / Équipe Formats d'Échange. Titre : La Théorie des Graphes (cours IT1 2002) Présentation de la Théorie des Graphes (cours IT1 2002) Date du document : 1996 (dernière modification : 15 mai 2002) Résumé : La théorie des graphes est utilisée dans de nombreux domaines pour schématiser des réseaux ou des relations. Elle décrit des graphes composés de sommets reliés par des arcs ou des arêtes. Les différentes notions mises en jeu, telles que la notion de connexité, permettent de résoudre des problèmes simples ou très complexes : comme par exemple la recherche d'un plus court chemin entre deux villes étapes. Les définitions de base, les théorèmes et les algorithmes les plus intéressants d'un point de vue pédagogique sont présentés dans ce document. Les ouvrages de C.Berge font office de référence. Mots clés : Thème principal : Théorie des graphes. Autres mots-clefs : sommets, arcs, connexité, graphe planaire, arbre ... La Théorie des Graphes, cours IT1 2002 IGN/ENSG/CPRI/SP page n° 3/65 Table des matières Remerciements .................................................................................................................................... 5 Bibliographie ....................................................................................................................................... 5 Avertissement ...................................................................................................................................... 6 Le vocabulaire employé ........................................................................................................... 6 Les limites de ce document...................................................................................................... 6 Domaines d'application de la théorie des graphes ............................................................................... 6 1. Définitions de base .......................................................................................................................... 7 1.1. "Deux définitions indissociables" pour les graphes.......................................................... 7 1.1.1. Définition "intuitive" d'un graphe ...................................................................... 7 1.1.2. Définition mathématique d'un graphe................................................................ 8 1.2. Ordre, orientation et multiplicité....................................................................................... 9 1.2.1. Ordre .................................................................................................................. 9 1.2.2. Orientation ......................................................................................................... 9 1.2.3. Multiplicité....................................................................................................... 10 1.3. Relations entre les éléments d'un graphe ........................................................................ 12 1.3.1. Relations entre sommets .................................................................................. 12 1.3.2. Relations entre arcs et sommets....................................................................... 14 1.3.3. Qualificatifs des graphes.................................................................................. 15 1.4. Matrices associées à un graphe ....................................................................................... 18 1.4.1. Matrice d'incidence sommet-arc ...................................................................... 18 1.4.2. Matrice d'adjacence ou d'incidence sommets-sommets ................................... 19 1.4.3. Forme condensée des matrices creuses ............................................................ 19 1.5. Vocabulaire lié à la connexité......................................................................................... 20 1.5.1. Chaîne, chemin, longueur ................................................................................ 20 1.5.2. Connexité ......................................................................................................... 21 1.5.3. Cycle et circuit ................................................................................................. 21 1.5.4. Cocycle et cocircuit.......................................................................................... 23 2. Cycles............................................................................................................................................. 25 2.1. Nombres cyclomatique et cocyclomatique ..................................................................... 25 2.1.1. Décomposition des cycles et des cocycles en sommes élémentaires ............... 25 2.1.2. Lemme des arcs colorés (Minty 1960)............................................................. 26 2.1.3. Base de cycles et base de cocycles................................................................... 28 2.2. Planarité .......................................................................................................................... 29 2.2.1. Graphe Planaire................................................................................................ 29 2.2.2. Formule d'Euler................................................................................................ 30 2.2.3. Théorème de Kuratowski (1930) ..................................................................... 31 2.2.4. Graphe Dual ..................................................................................................... 32 2.3. Arbre, forêt et arborescence............................................................................................ 33 2.3.1. Définitions........................................................................................................ 33 2.3.2. Propriétés ......................................................................................................... 34 2.3.3. Arbre maximal (ou couvrant)........................................................................... 35 3. Flots ............................................................................................................................................... 36 3.1. Définitions....................................................................................................................... 36 3.2. Recherche d'un flot maximum dans un réseau de transport............................................ 37 3.2.1. Définition ......................................................................................................... 37 3.2.2. Théorème de Ford-Fulkerson........................................................................... 37 3.2.3. Algorithme de Ford-Fulkerson......................................................................... 38 3.3. Recherche d'un flot compatible....................................................................................... 39 3.4. Application à la h-connexité........................................................................................... 40 3.5. Application aux couplages.............................................................................................. 41 La Théorie des Graphes, cours IT1 2002 IGN/ENSG/CPRI/SP page n° 4/65 4. Problèmes de cheminement ........................................................................................................... 43 4.1. Classification des problèmes mathématiques ................................................................. 43 4.2. Recherche des composantes connexes............................................................................ 43 4.2.1. Présentation des objectifs................................................................................. 43 4.2.2. Algorithme de Trémeaux-Tarjan...................................................................... 44 4.3. Recherche du plus court chemin..................................................................................... 46 4.3.1. Présentation des conditions.............................................................................. 46 4.3.2. Algorithme de Moore-Dijkstra......................................................................... 46 4.4. Recherche d'un arbre de poids extrémum ....................................................................... 47 4.4.1. Présentation des objectifs................................................................................. 47 4.4.2. Algorithme de Kruskal 1956............................................................................ 48 5. Problèmes Hamiltonien et Eulérien............................................................................................... 49 5.1. Problème Hamiltonien .................................................................................................... 49 5.1.1. Définitions........................................................................................................ 49 5.1.2. Condition nécessaire d'existence d'un cycle hamiltonien................................. 49 5.1.3. Condition suffisante d'existence d'un circuit hamiltonien................................ 50 5.1.4. Condition suffisante d'existence d'un cycle hamiltonien ................................. 52 5.2. Problème Eulérien........................................................................................................... 53 5.2.1. Définitions........................................................................................................ 53 5.2.2. Condition nécessaire et suffisante d'existence d'une chaîne eulérienne........... 53 5.2.3. Algorithme local pour tracer un cycle eulérien................................................ 54 5.2.4. Lien entre problème eulérien et hamiltonien.................................................... 54 6. Coloration ...................................................................................................................................... 55 6.1. Définitions....................................................................................................................... 55 6.2. Coloration des sommets.................................................................................................. 55 6.3. Coloration des arêtes....................................................................................................... 55 6.4. Propositions .................................................................................................................... 56 6.5. Le théorème des "4 couleurs".......................................................................................... 56 6.6. Graphe parfait ................................................................................................................. 56 7. Graphe d'intervalles et graphe triangulé ........................................................................................ 57 7.1. Définitions....................................................................................................................... 57 7.2. Propriétés ........................................................................................................................ 58 8. Hypergraphe................................................................................................................................... 59 8.1. Définitions....................................................................................................................... 59 8.2. Un exemple d'application : la méthode HBDS ............................................................... 60 Formulaire.......................................................................................................................................... 61 Index .................................................................................................................................................. 64 La Théorie des Graphes, cours IT1 2002 IGN/ENSG/CPRI/SP page n° 5/65 Remerciements Je tiens à remercier toutes les personnes qui m'ont aidé dans l'élaboration de ce document et particulièrement D.Richard (pour le prêt de ses livres) ainsi que A.Milledrogues et J.Trévisan (pour leur polycopié et leurs explications quant à l'attente des élèves ingénieurs des travaux). Bibliographie Graphes et Hypergraphes de C.Berge (Edition Dunod 1970) Graphes de C.Berge (Bordas 1983) Hypergraphes, Combinatoire des ensembles finis de C.Berge (Bordas 1987) Graphes et algorithmes de M.Gondran et M.Minoux (Eyrolles 1985) La Théorie des graphes, cours de M. Las Vergnas de A.Milledrogues et J.Trévisan (IGN/ENSG 1994) La Théorie des Graphes, cours IT1 2002 IGN/ENSG/CPRI/SP page n° 6/65 Avertissement Le vocabulaire employé Tous les ouvrages concernant la théorie des graphes se heurtent à un problème de vocabulaire... En effet, selon ses préoccupations, l'auteur est enclin à mettre en exergue soit l'aspect mathématique de la théorie des graphes, soit son aspect représentation figurative. Ainsi on rencontre plusieurs appellations pour le même élément, la même caractéristique ou la même relation. De plus, l'orientation d'un graphe n'est pas nécessaire pour l'étude de toutes les propriétés. Les différents auteurs ont donc choisi des termes pour décrire les mêmes propriétés dans un cas ou dans l'autre. On est donc confronté à un vocabulaire composé de mots ayant un sens générique et d'autres un sens plus spécifique. Pour rendre plus clair cette présentation de la théorie des graphes, j'ai donc choisi de garder le vocabulaire employé par C.Berge et de préciser pour chaque définition les limites de son application dans ce document. Les limites de ce document Ce document n'est pas un traité sur la théorie des graphes mais une présentation. Certains résultats ou phénomènes seront donc omis. De même, seuls seront fournis les démonstrations et les algorithmes les plus intéressants d'un point de vue pédagogique. Je préciserai autant que faire ce peut, où trouver tel ou tel complément d'informations. Domaines d'application de la théorie des graphes Les graphes (et par conséquent la théorie des graphes) sont utilisés dans de nombreux domaines. On peut donner quelques exemples : - les réseaux de communication : réseaux de routes représentés par une carte routière, réseaux de chemin de fer, de téléphone, de relais de télévision, réseaux électriques, réseaux des informations dans une organisation, etc. .. ; - la gestion de la production : graphes potentiels-étapes plus connu sous le nom de graphes PERT 1 ; - l'étude des circuits électriques : Kirchhof, qui a étudié les réseaux électriques, peut être considéré comme un des précurseurs de cette théorie ; - la chimie, la sociologie et l'économie : la notion de clique est un exemple de l'implication de la théorie des graphes dans ces disciplines. 1 "Programme Evaluation and Research Task" ou "Programme Evaluation Review Technique" La Théorie des Graphes, cours IT1 2002 IGN/ENSG/CPRI/SP page n° 7/65 1. Définitions de base 1.1. "Deux définitions indissociables" pour les graphes Comme on vient de le préciser au § "Avertissement", un graphe peut être défini de manière "intuitive" ou mathématique. Ces deux aspects sont indissociables et donnent les deux définitions suivantes (empruntées à C.Berge) : 1.1.1. Définition "intuitive" d'un graphe Définition : "Un graphe est un schéma constitué par un ensemble (ici supposé fini 1) de points et par un ensemble de flèches reliant chacune deux de ceux-ci. Les points sont appelés les sommets du graphe, et les flèches les arcs du graphe." Exemple : Dans le graphe de la figure 1, on a : - un ensemble de sommets : a,b, c,d,e, f, g, h { } - un ensemble d'arcs : 1,2,3,4,5,6,7,8 { } b e f c d g h a 1 2 3 4 5 6 7 8 9 Figure 1 : un exemple de graphe 1 Dans ce document, on s'intéressera principalement aux graphes finis bien que de nombreuses notions puissent être généralisées. La Théorie des Graphes, cours IT1 2002 IGN/ENSG/CPRI/SP page n° 8/65 Remarque : "La position des sommets et la forme des arcs sur une figure n'importe pas ; seul importe de savoir comment les sommets sont reliés". Les graphes des figures 1 et 2 sont uploads/Philosophie/ theorie-graphes.pdf