Remerciez-le!

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

Théorie des graphes: Concepts de base Différentes techniques de la Recherche op

Théorie des graphes: Concepts de base Différentes techniques de la Recherche opérationnelle • Programmation mathématique  modélisation mathématique – Programmation linéaire – Programmation linéaire en nombres entiers – Programmation non linéaire – … • Programmation par contraintes • Théorie des graphes • Modèles stochastiques • Simulation • Théorie des jeux • …  modélisation par les graphes • Structure • Connexions • Cheminements Un parc à optimiser…  Le parc SEERVADA offre à ses visiteurs des circuits de randonnée et des visites écologiques. Les voitures n’y sont pas admises, seules quelques pistes permettent aux petits trains transportant les touristes du parc de circuler entre les différents points de visite. Le point O est l’entrée du parc et le point T représente une très belle vue panoramique. O 3 4 2 1 5 A B C D E T 2 4 7 4 1 5 7 Le réseau routier du parc SEERVADA  Durant la haute saison, le nombre de touristes voulant emprunter le train pour aller de O à T augmente considérablement. Pour répondre à la demande, plusieurs chemins peuvent être empruntés indépendamment de leur longueur, mais le nombre de voyages de train possibles par jour est limité pour chaque chemin. Comment choisir les voyages à faire sur les différents chemins pour maximiser le nombre total de voyages en respectant les limites établies?  Problème de flot maximum  Problème d’arbre couvrant de poids minimum  Problème de plus court chemin Le parc fait face à trois problèmes :  Quel est le chemin offrant la distance minimale entre l’entrée et la vue panoramique?  Des lignes téléphonique doivent être installées pour assurer la connexion des stations entre elles. Pour des raisons budgétaires et environnementales, les lignes doivent longer juste ce qu’il faut de pistes pour assurer le lien entre deux points de visite quelconques. Quelles pistes choisir afin de minimiser le nombre de kilomètres de lignes installées? Définition • La théorie des graphes dispose d’un certain nombres d’outils de modélisation permettant de représenter simplement la structure, les connexions, les cheminements possibles dans un système complexe en exprimant les relations entre ses composantes Exemple : réseau de communication, réseau routier ou ferroviaire, diagramme de succession des tâches pour un projet, etc. Problème ayant une écriture formelle compliqué Théorie des Graphes Définition: Graphes  Les graphes font l’objet d’une branche des mathématiques discrètes appelée "théorie des graphes" développée dans les années 50 par le français Claude Berge  Graphes : ensemble de points et de flèches représentation graphique  Graphes : des objets, appelés nœuds, reliés par des connexions orientées (arcs) ou bien non orientés (arêtes) Noté : G = (X,U) avec X : ensemble discret, fini de sommets ou nœuds U : ensemble d’arcs constitué par des paires de sommets (i,j) de X Si N = |X| est le nombre de sommets alors G est d’ordre N Définition : Graphes orientés Un graphe orienté G = (X,U) est défini par un ensemble X = {x1, x2, ...., xn} de n nœuds (ou sommets) et un ensemble U = {u1, u2, ...., um} de m connexions orientées entre nœuds appelées arcs. La représentation graphique suivante est celle d’un graphe orienté G = (X,U) qui peut être décrit indépendamment du dessin en précisant X et U. 6 1 4 2 3 5 • X = {1,2,3,4,5,6}, on a n = 6 nœuds (on dit aussi que G est d’ordre 6) • U = {(1,4),(1,5),(2,2),(2,4),(3,4),(3,5),(4,2),(4,6),(5,2),(6,1),(6,3)}, on a m = 11 arcs Définition : Graphes orientés • Un arc u = (i,j) est dit orienté si i est son extrémité initiale et j son extrémité terminale. u est incident extérieurement au sommet i et incident intérieurement à j. i est un précédent ou prédécesseur de j et j est un suivant ou successeur de i. L’ensemble des successeurs de i est noté (i) ; l’ensemble des prédécesseurs de i est noté -1(i). • Un graphe est dit orienté si tous ses arcs sont orientés • Un arc est non orienté si le flux correspondant est bidirectionnel. On parle d’arrête est non plus d’arc Définition : Graphes orientés 6 1 4 2 3 5 • L’arc (6,3) a pour extrémité initiale le nœud 6 et pour extrémité terminale le nœud 3 • 3 est le successeur de 6 et 6 est le prédécesseur de 3 • Les deux nœuds, reliés par au moins un arc, sont dits voisins • L’arc (2,2) est une boucle • Deux arcs ayant au moins un nœud commun sont dits adjacents : (6,3) et (3,5), mais aussi (6,3) et (6,1) ou (4,2) et (2,4) • (i) représente l’ensemble des successeurs d’un nœud i et -1(i) l’ensemble des prédécesseurs : (1) = {4,5} et -1(1) = {6} • On note d+(i) le demi-degré extérieur du nœud i, c’est-à-dire son nombre de successeurs : d+(4) = 2. d-(i) est le demi-degré intérieur (nombre de prédécesseurs) : d-(4) = 3. Le degré d(i) vaut d+(i)+d-(i) (un nœud avec une boucle y est compté deux fois ) Définition : Graphes non orientés Parfois, l’orientation ne nous intéresse pas : on veut juste savoir quelles paires de nœuds sont connectées ou pas. On a alors un graphe non orienté G = (X,E) dont les m connexions sont des arêtes (edges). Elles sont notées entre crochets pour les distinguer des arcs : [1,4] ou [4,1] représente la même arête 6 1 4 2 3 5 6 1 4 2 3 5 Graphe orienté G=(X,U) Graphe non orienté H=(X,E) associé à G Définition : Graphes valués Les arcs d'un graphe peuvent être munis de coûts ou poids au sens large : coûts de transport, distances, durées, intensités de courant. Le graphe est alors valué, on le note G = (X,U,C), C étant une application qui à tout arc (i,j) associe un coût C((i,j)) ou pour abréger Cij 6 1 4 2 3 5 3 2 5 3 2 5 9 3 1 10 7 Définition : Graphe partiel et sous graphe Définitions: Chaîne – Cycle – Chemin – Circuit Chaîne – Cycle • Une chaîne entre deux nœuds est une séquence d’arêtes telle que chaque arête de la séquence ait une extrémité commune avec l’arête suivante. • Un cycle est une chaîne dont les extrémités coïncident. Chemin – Circuit • Un chemin est une chaîne dont les arcs sont orientés dans le même sens. • Un circuit est un chemin dont les extrémités coïncident. Définitions: Chaîne – Cycle – Chemin – Circuit • Le graphe représenté par les arcs (C,A), (C,E) et (E,D) représente une chaîne reliant A et D • Le graphe représenté par les arcs (A,B), (B,C), (C,E) et (E,D) représente un chemin reliant A et D • (C,B), (B,D), (E,D) et (C,E) constituent un cycle • (A,B), (B,C) et (C,A) constituent un circuit A B C D E • Que constituent : 1. (A,B), (B,C) et (C,A) 2. (C,B), (B,D), (E,D) et (C,E) 3. (A,B), (B,C), (C,E) et (E,D) 4. (C,A), (C,E) et (E,D) uploads/Philosophie/ ro-graphe-seance-1.pdf