Remerciez-le!

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

Theorie des graphes Stéphane Pelle École Nationale des Sciences Géographiques Institut Géographique National GEOMATIQUE LA THÉORIE DES GRAPHES Cours Ingénieur ère année ÉCOLE NATIONALE DES SCIENCES GEOGRAPHIQUES et avenue Blaise Pascal Marne la Vallée Ced

Stéphane Pelle École Nationale des Sciences Géographiques Institut Géographique National GEOMATIQUE LA THÉORIE DES GRAPHES Cours Ingénieur ère année ÉCOLE NATIONALE DES SCIENCES GEOGRAPHIQUES et avenue Blaise Pascal Marne la Vallée Cedex www ensg ign fr ? IGN C CTable des matières Avertissement et Domaines d'application Chapitre I Dé ?nitions de base Partie A Deux dé ?nitions indissociables pour les graphes Dé ?nition intuitive d'un graphe Dé ?nition mathématique d'un graphe Partie B Ordre orientation et multiplicité Ordre Orientation Multiplicité Partie C Relations entre les éléments d'un graphe Relations entre sommets Relations entre arcs et sommets Quali ?catifs des graphes Partie D Matrices associées à un graphe Matrice d'incidence sommet-arc Matrice d'adjacence ou d'incidence sommets-sommets Forme condensée des matrices creuses Partie E Vocabulaire lié à la connexité Cha? ne chemin longueur Connexité Cycle et circuit Cocycle et cocircuit Chapitre II Cycles Partie A Nombres cyclomatique et cocyclomatique Décomposition des cycles et des cocycles en sommes élémentaires Lemme des arcs colorés Minty C GEOMATIQUE Base de cycles et base de cocycles Partie B Planarité Graphe Planaire Formule d'Euler Théorème de Kuratowski Graphe Dual Partie C Arbre forêt et arborescence Dé ?nitions Propriétés Arbre maximal ou couvrant Chapitre III Flots Partie A Dé ?nitions Partie B Recherche d'un ot maximum dans un réseau de transport Dé ?nition Théorème de Ford-Fulkerson Algorithme de Ford-Fulkerson Partie C Recherche d'un ot compatible Partie D Application à la h-connexité Partie E Application aux couplages Chapitre IV Problèmes de cheminement Partie A Classi ?cation des problèmes mathématiques Partie B Recherche des composantes connexes Présentation des objectifs Algorithme de Trémeaux-Tarjan Partie C Recherche du plus court chemin Présentation des conditions Algorithme de Moore-Dijkstra Partie D Recherche d'un arbre de poids extrémum Présentation des objectifs Algorithme de Kruskal Chapitre V Problèmes Hamiltonien et Eulérien Partie A Problème Hamiltonien Dé ?nitions Condition nécessaire d'existence d'un cycle hamiltonien CTable des matières Condition su ?sante d'existence d'un circuit hamiltonien Condition su ?sante d'existence d'un cycle hamiltonien Partie B Problème Eulérien Dé ?nitions Condition nécessaire et su ?sante d'existence d'une cha? ne eulérienne Algorithme local pour tracer un cycle eulérien Lien entre problème eulérien et hamiltonien Chapitre VI Coloration Partie A Dé ?nitions Partie B Coloration des sommets Partie C Coloration des arêtes Partie D Propositions Partie E Le théorème des couleurs Partie F Graphe parfait Chapitre VII Graphe d'intervalles et graphe triangulé Partie A Dé ?nitions Partie B Propriétés Chapitre VIII Hypergraphe Partie A Dé ?nitions Partie B Un exemple d'application la méthode HBDS Chapitre IX Formulaire Partie A Formulaire Bibliographie Signi ?cation des sigles C CPréambule Avertissement et Domaines d'application Avertissement Le vocabulaire employé Tous les ouvrages concernant la théorie des graphes se heurtent à un problème de vocabulaire En e ?et 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 ?gurative 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