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 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 1 GEN

THEORIE DES GRAPHES GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 1 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 2 GENERALITES RESEAU, THEORIE DES GRAPHES, ORIGINE ET DEFINITION Dans les domaines de la Géographie, de l’Aménagement, et de l’Urbanisme, la théorie des graphes est utilisée pour aborder des questions posées dans le domaine des réseaux (qu’il s’agisse de réseaux de transport et de communication ou encore de réseaux sociaux). La démarche générale est fondée sur la traduction de ces problèmes dans le langage mathématique de la théorie des graphes de manière à pouvoir les traiter en utilisant, par exemple, les propriétés de connectivité, ou encore en explorant les chemins minimaux. C’est la raison pour laquelle, dans ses applications aux sciences humaines et sociales, la théorie des graphes traite principalement des propriétés mathématiques et beaucoup moins de la représentation graphique des noeuds et des arcs1. En retournant vers les questions graphiques qui lui ont donné naissance, c’est le versant de la théorie des graphes qui a trait à la représentation (la réalisation des graphe) que nous voulons développer ici, dans ses applications à des problématiques de l’analyse spatiale. La théorie des graphes étant particulièrement adaptée à la modélisation des réseaux de transport, la représentation du graphe du réseau peut constituer une piste de travail pour répondre à la difficile question de la représentation des distances. 1 Quand on étudie la théorie des graphes, une des seules propriétés qui a trait à leur représentation –leur réalisation– est la notion de graphe planaire. Un graphe est dit planaire si l’on peut le dessiner sur un plan de sorte que les sommets soient des points distincts, les arêtes des courbes simples et que deux arêtes ne se rencontrent pas en dehors de leurs extrémités. GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 3 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 4 Qu'est ce qu'un graphe? C'est en 1822 que le mot "graphe" est introduit par l'Anglais J.J.Sylvester, et en 1936 que parait le premier livre sur la théorie des graphes, écrit par D.King. Un graphe est un dessin géométrique défini par la donnée d'un ensemble de points (appelés sommets ou noeuds), reliés entre eux par un ensemble de lignes ou de flèches (appelées arêtes ou arcs). Chaque arête a pour extrémités deux points, éventuellement confondus. Les graphes peuvent servir à représenter un grand nombre de situations courantes comme: • Les liens routiers • Les réseaux de communication • Les circuits électriques • Les liens entre diverses personnes ou entités administratives. Exemple: La figure suivante représente un plan de circulation à sens unique d'une ville ou chaque localité est représentée par un point appelé sommet et chaque route par un arc orienté indiquant le sens de la circulation. Ainsi les notions qu'on peut définir sur un graphe, vont servir à résoudre certains problèmes liés à différents domaines. GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 5 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 6 Née de la résolution de questions concrètes difficilement solubles graphiquement (comme le problème du cheminement par les ponts de Königsberg résolu par Euler, ou le problème des quatre couleurs mis à jour pour la première fois par le cartographe Guthrie en 1852) la théorie des graphes compose un appareil mathématique qui permet d’appréhender des problèmes dans un champ très vaste. Les ponts de Königsberg GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 7 Pour connaître objectivement et analyser la structure d'un réseau (sa topologie), il doit être représenté sous forme de graphe. On fait remonter la théorie des graphes au problème dit "des ponts de Königsberg" résolu par Leonhard Euler en 1736. Il s'énonçait ainsi : est-il possible, en partant d'une zone de la ville, de retourner dans la même zone en traversant chacun de ses sept ponts une fois et une seule ? En 1822, le mot "graphe" est introduit par l'anglais J.J. Sylvester et, en 1936, paraît un premier livre sur la théorie des graphes écrit par D. König. GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 8 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 9 HISTOIRE 1 2 3 4 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 10 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 11 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 12 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 13 Les graphes modélisent de nombreuses situations concrêtes où interviennent des objets en interaction. •Les interconnexions routière, ferrovière ou aériennes entre différentes agglomérations, •Les liens entre les composants d'un circuit électronique, •Le plan d'une ville et de ses rues en sens unique,... Les graphes permettent de manipuler plus facilement des objets et leurs relations avec une représentation graphique naturelle. L'ensemble des techniques et outils mathématiques mis au point en Théorie des Graphes permettent de démontrer facilement des propriétés, d'en déduire des méthodes de résolution, des algorithmes, ... • Quel est le plus court chemin (en distance ou en temps) pour se rendre d'une ville à une autre? • Comment minimiser la longueur totale des connexions d'un circuit? • Peut-on mettre une rue en sens unique sans rendre impossible la circulation en ville? GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 14 Un graphe permet de décrire un ensemble d'objets et leurs relations, c'est à dire les liens entre les objets. •Les objets sont appelés les nœuds, ou encore les sommets du graphe. •Un lien entre deux objets est appelé une arête Un graphe G est un couple (V,E) où •V est un ensemble (fini) d'objets. Les éléments de V sont appelés les sommets du graphe. •E est sous-ensemble de VxV. Les éléments de E sont appelés les arêtes du graphe. Une arête e du graphe est une paire e=(x,y) de sommets. Les sommets x et y sont les extrémités de l'arête. GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 15 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 16 DEFINITIONS GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 17 Un exemple de graphe à 8 sommets, nommés a à h, comportant 10 arêtes. G=(V,E) V={ a, b, c, d,e, f, g, h } E={ (a,d),(b,c), (b,d),(d,e), (e,c),(e,h), (h,d),(f,g), (d,g),(g,h) } GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 18 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 19 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 20 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 21 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 22 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 23 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 24 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 25 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 26 PROPRIETES DESCRIPTIVES GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 27 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 28 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 29 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 30 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 31 PROPRIETES STRUCTURELLES ELEMENTAIRES GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 32 GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 33 Degré • Deux sommets x et y sont adjacents si il existe l'arête (x,y) dans E. Les sommets x et y sont alors dits voisins • Une arête est incidente à un sommet x si x est l'une de ses extrémités. • Le degré d'un sommet x de G est le nombre d'arêtes incidentes à x. Il est noté d(x). Pour un graphe simple le degré de x correspond également au nombre de sommets adjacents à x. GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 34 Pour caractériser de manière moins locale la structure d'un graphe, il est possible de rechercher des parties remarquables du graphe, en restreignant soit l'ensemble des sommets (sous-graphe), soit l'ensemble des arêtes (graphe partiel). • Un sous-graphe de G consiste à considérer seulement une partie des sommets de V et les liens induits par E. Par exemple si G représente les liaisons aériennes journalières entre les principales villes du monde, un sous-graphe possible est de se restraintre aux liaisons journalières entre les principales villes européennes. • Un graphe partiel de G consiste à ne considérer qu'une partie des arêtes de E. En reprenant le même exemple, un graphe partiel possible est de ne considérer que les liaisons journalières de moins de 3 heures entre les principales villes du monde. GENIE URBAIN / THEORIE DES GRAPHES / Mlle, BENZAOUI.A 35 Pour un graphe G = (V,E) • Un sous-graphe de G est un graphe H=(W, E(W)) tel que W est un sous-ensemble de V, et E(W) sont les arêtes induites par E sur W, c'est à dire les arêtes de E dont les 2 extrémité sont des sommets de W. • Un graphe partiel de G est un graphe I=(V,F) tel que F est un sous ensemble de E. Un sous-graphe H uploads/Ingenierie_Lourd/ graph-theory-3eme.pdf