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 École Nationale des Sciences Géographiques, Institut Géographiqu

Stéphane Pelle École Nationale des Sciences Géographiques, Institut Géographique National GEOMATIQUE LA THÉORIE DES GRAPHES Cours Ingénieur 1ère année ÉCOLE NATIONALE DES SCIENCES GEOGRAPHIQUES. 6 et 8 avenue Blaise Pascal 77455 Marne la Vallée Cedex 2 www.ensg.ign.fr © IGN 2005 Table des matières Avertissement et Domaines d'application.............................. 7 Chapitre I. Définitions de base........................................... 9 Partie A. "Deux définitions indissociables" pour les graphes................ 9 1. Définition "intuitive" d'un graphe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2. Définition mathématique d'un graphe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Partie B. Ordre, orientation et multiplicité.................................... 11 1. Ordre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2. Orientation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3. Multiplicité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Partie C. Relations entre les éléments d'un graphe......................... 15 1. Relations entre sommets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2. Relations entre arcs et sommets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3. Qualificatifs des graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Partie D. Matrices associées à un graphe................................... 20 1. Matrice d'incidence sommet-arc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2. Matrice d'adjacence ou d'incidence sommets-sommets. . . . . . . . . . . . . . . . . . . . 21 3. Forme condensée des matrices creuses. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Partie E. Vocabulaire lié à la connexité...................................... 22 1. Chaîne, chemin, longueur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2. Connexité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3. Cycle et circuit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4. Cocycle et cocircuit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Chapitre II. Cycles......................................................... 29 Partie A. Nombres cyclomatique et cocyclomatique......................... 29 1. Décomposition des cycles et des cocycles en sommes élémentaires. . . . . . . . 29 2. Lemme des arcs colorés (Minty 1960). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3. Base de cycles et base de cocycles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Partie B. Planarité............................................................33 1. Graphe Planaire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2. Formule d'Euler. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3. Théorème de Kuratowski (1930). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4. Graphe Dual. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Partie C. Arbre, forêt et arborescence....................................... 37 1. Définitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2. Propriétés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3. Arbre maximal (ou couvrant). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 Chapitre III. Flots........................................................... 41 Partie A. Définitions.......................................................... 41 Partie B. Recherche d'un flot maximum dans un réseau de transport....... 42 1. Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2. Théorème de Ford-Fulkerson. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3. Algorithme de Ford-Fulkerson. . . . . . . . . uploads/Science et Technologie/ theorie-des-graphes.pdf