Remerciez-le!

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

rcp101 cours1 theorie des graphes

Unité d ? Enseignement RCP Recherche Opérationnelle et Aide à la Décision Cours - Théorie des graphes Conservatoire National des Arts et Métiers E Soutil et F Badran CUE RCP ?? Recherche Opérationnelle et Aide à la Décision ?? Plan du cours ? Partie - Eléments de Théorie des Graphes Généralités fermeture transitive et connexité Chemins de longueur optimale ? Partie ?? Ordonnancement Méthode PERT Méthode MPM ? Partie ?? Programmation linéaire Modélisation Méthode du simplexe Dualité ? Partie Processus de Markov et ?les d ? attente ? Partie Optimisation multicritères RCP ?? Partie ?? Théorie des Graphes CBibliographie ? 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 RCP ?? Partie ?? Théorie des Graphes CPartie ?? Eléments de Théorie des Graphes ?? Généralités et dé ?nitions ? 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 è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 RCP ?? Partie ?? Théorie des Graphes CLa Théorie des Graphes Généralités et dé ?nitions ? 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 Arcs U a b c d e f g ? Notation l ? arc u se note u x y ? Le nom des sommets est quelconque chi ?res lettres mot les arcs sont rarement nommés désignés par leurs extrémités initiale et terminale RCP ?? Partie ?? Théorie des Graphes CLa Théorie des Graphes Généralités et dé ?nitions ? 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é RCP ?? Partie ?? Théorie des Graphes d d- d CLa Théorie des Graphes Généralités et dé ?nitions ? 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