Remerciez-le!

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

Unité d’Enseignement RCP101 : Recherche Opérationnelle et Aide à la Décision Co

Unité d’Enseignement RCP101 : Recherche Opérationnelle et Aide à la Décision Cours 1 - Théorie des graphes Conservatoire National des Arts et Métiers E. Soutil et F. Badran UE RCP101 – Recherche Opérationnelle et Aide à la Décision – Plan du cours Partie 1- Eléments de Théorie des Graphes Généralités, fermeture transitive et connexité Chemins de longueur optimale Partie 2 – Ordonnancement Méthode PERT Méthode MPM Partie 3 – Programmation linéaire Modélisation Méthode du simplexe Dualité Partie 4 : Processus de Markov et files d’attente Partie 5 : Optimisation multicritères RCP101 – Partie 1 – Théorie des Graphes 2 Bibliographie RCP101 – Partie 1 – Théorie des Graphes 3 Précis de Recherche Opérationnelle – Editions Dunod – Auteurs : R. Faure, B. Lemaire, Ch. Picouleau Méthodes d’optimisation combinatoire – Editions Masson – Auteurs : I. Charon, A. Germa, O. Hudry Partie 1 – Eléments de Théorie des Graphes – Généralités et définitions Les graphes : Un outil irremplaçable pour la modélisation des systèmes réels Qu’est-ce qu’un graphe ? « Des points et des flèches » Point de vue mathématique : une relation binaire Point de vue pratique : représentation abstraite d’un réseau (de télécommunication par exemple) Utilisés dans des domaines très variés : économie, informatique, industrie, chimie, sociologie. RCP101 – Partie 1 – Théorie des Graphes 4 La Théorie des Graphes Généralités et définitions Graphe orienté : G = (X, U) X : ensemble de sommets. |X|: ordre de G (noté n) U : ensemble d’arcs. |U|: taille de G (notée m) Représentation graphique : Sommets : X = {1, 2, 3, 4} Arcs : U = {a, b, c, d, e, f, g} Notation : l’arc u se note u = (x,y) Le nom des sommets est quelconque (chiffres, lettres, mot), les arcs sont rarement nommés (désignés par leurs extrémités initiale et terminale) RCP101 – Partie 1 – Théorie des Graphes 5 La Théorie des Graphes Généralités et définitions RCP101 – Partie 1 – Théorie des Graphes 6 Soit G = (X,U) un graphe orienté et u = (x,y) un arc de G : x : extrémité initiale de u ; y : extrémité terminale de u x et y sont dits adjacents ; u est incident intérieurement à y, extérieurement à x u est aussi dit adjacent à x et y deux arcs sont adjacents s’ils ont une extrémité commune d+(x) : demi-degré extérieur de x = nb d’arcs qui partent de x d-(x) : demi-degré intérieur de x = nb d’arcs qui arrivent en x d(x) = d+(x)+ d-(x) : degré de x G est dit régulier si tous ses sommets ont le même degré d+(2) = 4 d-(2) =2 d(2)=6 La Théorie des Graphes Généralités et définitions RCP101 – Partie 1 – Théorie des Graphes 7 Soit G = (X,U) un graphe orienté y est successeur de x si (x,y)U +(x) : ensemble des successeurs de x y est prédécesseur de x si (y,x)U -(x) : ensemble des prédécesseurs de x y est voisin de x si y (x)=+(x)-(x) c-à-d si y est successeur ou prédécesseur de x Un graphe est dit simple (ou encore 1-graphe) s’il ne possède pas deux arcs ayant la même extrémité initiale et la même extrémité terminale : U X × X Une boucle est un arc dont l’extrémité initiale est aussi l’extrémité terminale (ex : c = (2,2) ) On s’intéresse le plus souvent aux graphes simples sans boucle. Graphe non simple = multigraphe Graphe valué : les arcs portent une information appelée valuation (distance, coût, gain, …) Un 2-graphe (multigraphe) Un graphe simple valué La Théorie des Graphes Généralités et définitions RCP101 – Partie 1 – Théorie des Graphes 8 +(2) = {1, 2, 3} : ensemble des successeurs de 2 -(2) = {1, 2} : ensemble des prédécesseurs de 2 (2)={1, 2, 3} : ensemble des voisins de 2 +(D) = {A, C} : ensemble des successeurs de D -(D) = {B} : ensemble des prédécesseurs de D (D)={A, B, C} : ensemble des voisins de D Un 2-graphe (multigraphe) Un graphe simple valué La Théorie des Graphes Généralités et définitions RCP101 – Partie 1 – Théorie des Graphes 9 Un chemin dans G = (X, U) : séquence d’arcs u1, u2, …, um de U t.q. l’extrémité terminale d’un arc coïncide avec l’extrémité initiale de l’arc suivant : Pour tout k (1≤k ≤m-1) on a : extrémité terminale de uk = extrémité initiale de uk+1 Exemple : ((D,A),(A,B),(B,C)) noté DABC Un chemin peut être : simple : ne passe pas deux fois le même arc élémentaire : ne passe pas deux fois par le même sommet DABA : chemin simple, non élémentaire élémentaire simple La Théorie des Graphes Généralités et définitions RCP101 – Partie 1 – Théorie des Graphes 10 Un circuit : chemin dont l’origine et la fin coïncident extrémité initiale de u1 = extrémité terminale de um DABD : circuit élémentaire DABDABD : circuit non élémentaire élémentaire simple La Théorie des Graphes Généralités et définitions RCP101 – Partie 1 – Théorie des Graphes 11 Graphes non orientés : G = (X, A) X : ensemble de sommets A : ensemble d’arêtes (arc sans orientation) Deux arêtes ayant une extrémité commune dont dites adjacentes (Ex : [a,b] et [b,c] ) Une chaîne : séquence d’arêtes t.q. toute arête de la séquence est adjacente à l’arête qui la suit et à celle qui la précède. Exemple : [acdb] ou ([a,c], [c,d], [b,d]) Chaîne dans un graphe orienté : DCBA Cycle : chaîne dont les deux extrémités coïncident (Ex : [eacdbe]) Graphe non orienté Graphe orienté Chaîne eulérienne : passant une fois et une seule par chaque arête Exemple : les sept ponts de Königsberg. Peut-on se promener dans la ville en traversant chaque pont une et une seule fois ? (Euler, 1736) Théorème d’Euler : Un multigraphe connexe admet une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est 0 ou 2 La Théorie des Graphes Généralités et définitions RCP101 – Partie 1 – Théorie des Graphes 12 La Théorie des Graphes Généralités et définitions RCP101 – Partie 1 – Théorie des Graphes 13 Orienté Non orienté Arc Arête Chemin (la notion de chaîne existe aussi dans les graphes orientés en faisant abstraction de l’orientation) Chaîne Circuit (la notion de cycle existe aussi) Cycle Généralités et définitions – Connexité RCP101 – Partie 1 – Théorie des Graphes 14 Soit G = (X, U) un graphe, orienté ou non. On définit la relation binaire R sur X, dite relation de connexité par : x R y si et seulement si x et y sont reliés par une chaîne dans G. R est une relation d’équivalence (réflexive, symétrique, transitive), dont les classes d’équivalence sont appelées composantes connexes de G G est dit connexe s’il ne possède qu’une unique composante connexe Un graphe comportant 3 composantes connexes La Théorie des Graphes Généralités et définitions : les arbres RCP101 – Partie 1 – Théorie des Graphes 15 Définition : un arbre est un graphe connexe et sans cycle. Une forêt est un graphe sans cycle. Propriété : Soit G = (X, U) un graphe d’ordre n. 1. Si G est connexe, |U| ≥ n-1 2. Si |U| ≥ n, G possède au moins un cycle Un arbre Une forêt Généralités et définitions – Forte connexité (graphes orientés uniquement) RCP101 – Partie 1 – Théorie des Graphes 16 Soit G = (X, U) un graphe, orienté. On définit la relation binaire RFC sur X, dite relation de forte connexité par : x RFC y si et seulement s’il existe un circuit de G contenant x et y ou x=y. RFC est une relation d’équivalence (réflexive, symétrique, transitive), dont les classes d’équivalence sont appelées composantes fortement connexes de G G est dit fortement connexe s’il ne possède qu’une unique composante fortement connexe Il existe un algorithme permettant de déterminer les composantes fortement connexes d’un graphe orienté. Exemple de graphe orienté comportant deux composantes fortement connexes (entourées). Ce graphe n’est donc pas fortement connexe. Forte connexité et graphe réduit RCP101 – Partie 1 – Théorie des Graphes 17 Soit G un graphe orienté admettant p composantes fortement connexes : C1, C2, …, Cp On définit le graphe réduit de G (noté GR) par GR = (XR, UR), avec : XR = {C1,C2,…,Cp}                  j i j i C C G U C C dans terminale extrémité son et connexe fortement composante la dans initiale extrémité son ayant dans arc un moins au existe Il ) , ( arc L' R Forte connexité et graphe réduit RCP101 – Partie 1 – Théorie des Graphes 18 Exemple : Résultat 1 : Le graphe réduit est un graphe sans circuit Représentation des graphes : matrice binaire RCP101 – Partie 1 – Théorie des Graphes 19 Soit G = (X,U) un graphe orienté ayant n sommets. On définit la matrice binaire n × n associée : M=[mij] uploads/Philosophie/ 1-rcp101-cours1-theorie-des-graphes.pdf