Remerciez-le!

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

-1- FACULTE DES SCIENCES ECONOMIQUES, SOCIALES ET DE GESTION DE REIMS INSTITUT

-1- FACULTE DES SCIENCES ECONOMIQUES, SOCIALES ET DE GESTION DE REIMS INSTITUT REMOIS DE GESTION Seconde année de Master Management Cours de Monsieur GAIGNETTE année universitair e 2009 -20 l0 RECHERCHE OPERATIONNELLE / METHODES D'AIDE A LA DECISION Support de cours numéro 0 RAPPELS : ELEMENTS DE LA THBORIE DES GRAPHES Section I - Notion de base en théorie des graphes. .............3 I.1 - Graphes orientés ......................3 I.2-Entrée, sortie, boucle, chemin, circuit, etc ........... .......3 I.2 - Graphes non orientés..... ...........5 Section II -Les différentes représentations d'un graphe orienté ..........5 II.1 - Représentation sagittale ..........6 II.2- Présentation algébrique ............6 II.3 - Matrice booléenne. ..................6 II.4 - Dictionnaire des suivants .....-......... ..........7 II.5 - Dictionnaire des précéden1s............... .......7 Section III - Niveaux ou rangs des sommets d'un graphe orienté 10 Série d'exercices Université de Reims - Faculté des Sciences Economiques, Sociales et de Gestion - Antonin Gaignette -2- ELEMENTS DE LA THEORIE DES GRAPHES Commençons par un exemple introductif : un agent commercial part de Paris pour vendre des produits à des magasins situés dans trois villes de Province. I1 connaît la durée approximative des déplacements entre les villes (en heures) et cherche dans quel ordre il doit les visiter afin de perdre le moins de temps possible. On peut représenter le problème sous la forme d'un schéma formé de points, appelés sommets, et de flèches, dénommées arcs. fu,r*r*hoh- ç,,[tA" I' La durée du trajet << aller > peut différer de celle du << retour >> en raison de travaux, etc. Les longueurs des flèches ne sont pas proportionnelles au temps. Il est possible de représenter le problème de façon matricielle (lecture dans le sens ( colonne - ligne >) : Toute une série de problèmes peut se représenter ainsi par un schéma formé de points réunis par des segments orientés ou non. La résolution de ces problèmes (problèmes de circulation dans un réseau ou problèmes de traitement complexe d'opérations successives) a conduit à l'élaboration d'une théorie mathématique spécifique dans le cadre de la recherche opérationnelle : la théorie des graphes. C'est I'ensemble constitué des points et des segments que I'on appelle un graphe. Le concept de graphe permet de schématiser les liaisons, les possibilités de communication et les relations d'ordre d'une structure. Il offre en plus la possibilité d'en étudier l'évolution. P A B C P 0 5 4 2 A 4 0 2 3 B 4 2 0 2 C 1 3 3 0 Université de Reims - Faculté des Sciences Economiques, Sociales et de Gestion - Antonin Gaignette t -3- Section I - Notion de base en théorie des graphes I.1 - Graphes orientés Un graplre orienté est défini par la connaissance de deux ensembles : ' o le premier est constitué d'éléments appelés sommets, o le second est composé d'arcs, un axc étant un couple orienté de sommets. Soit G un graphe. On note G : (X, Y), X étant I'ensemble des sommets et Y celui des arcs. Ainsi, si: o X: (4, B, C, D, E) o y:(A-A; A-B; B-C; C-C; C-B; C-D; C-E; D-D; D-E) Il est possible de représenter le graphe G: (X, 9 de la manière suivante : / A t\ l_) ['\ /'\ \\/)\,r --z ,_,( U- +=-r Dans cet exemple, I'arc A-B a pour origine le sommet A et pour extrémité le sommet B. On dit aussi que B est un suivant (ou successeur) de A et que A est un précédent (ou antécédent) de B. r."_rclr*Ëe^c *F 7r_*7",., I.2 - Entrée. sortie. boucle. chemin" circuit. etc ... Un sommet est une entrée (une racine) s'il ne possède pas de précédent. Dans l'exemple ci- dessus, le sommet A est une entrée. Un sommet est une sortie s'il ne possède pas de suivant. Toujours dans le même exemple, le sommet E est une sortie. Une boucle est un arc dont les extrémités sont confondues. Les arcs A-A, C-C et D-D sont des boucles. Un chemin est une succession d'arcs (ou une suite de sommets) tels que I'extrémité de chacun coihcide avec I'origine du suivant. Ainsi, A-A-B-C-E est un chemin. f6 - nelli s On définit comme antérieurs d'un sommet tous les sommets qui le précèdent immédiatement ou non. Ainsi, toujours dans notre exemple, le sommet D a comme antérieurs les sommets A, B et C puisqu'il est possible d'emprunter le chemin A-B-C-D. Toutefois, seul le sommet C est un précédent de D puisqu'il le précède immédiatement. Université de Reims - Faculté des Sciences Economiques, Sociales et de Gestioa - Antonin Gaignette -4- Un circuit est un chemin tel que I'origine du premier arc coihcide avec I'extrémité du dernier. Autrement dit, un circuit est un chemin qui revient à son point de départ. Le chemin C-B-C est un circuit. Un chemin simple est un chemin qui ne passe pas plus d'une fois par ihaque arc ; A-A-B-C-B est un chemin simple. Un chemin élémentaire est un chemin qui ne passe pas plus d'une fois par chaque sommet; A- B-C est un chemin élémentaire. Un graphe connexe est un graphe dont les sommets sont tels qu'il existe un chemin les reliant tous ; A-A-B-C-D-E par exemple. Un chemin hamiltonien est un chemin qui passe une fois et une seule par chaque sommet du graphe ; A-B-C-D-E par exemple. Un chemin eulérien est un chemin qui passe une fois et une seule par chaque arc ; il n'y en a pas dans notre exemple. Un graphe partiel G'd'un graphe G: (X, Y) est un graphe dont les sommets sont ceux de G et dont I'ensemble des arcs est inclus dans Y. G': (X', y') avec y'<y j) Un sous-graphe G' dlun graphe G : (X, Y) est un graphe dont I'ensemble des sommets est inclus dans X et dont les arcs, ou arêtes, sont ceux dont les extrémités se trouvent dans X'. G': (X', y') avec X'<X -(\ / \l A rc UU Un arbre est un graphe connexe sans circuit. Notre exemple est un arbre. Un arbre à n sommets aura donc (n - 1) arcs. B t \ \c U Université de Reims - Faculté des Sciences Economiques, Sociales et de Gestion - Antonin Gaignette -5- Une arborescence est un graphe orienté dont chaque sommet est I'exfiémité d'au plus un arc. Il possède donc toujours un sommet sans précédent, autrement dit une entrée, et il existe, pou tout sommet, un chemin unique reliant I'entrée à ce sommet. "'-t I DJ ,/\ GH EF /\ /r I.2 - Graphes non orientés On parle de graphe non orienté lorsque le graphe n'est pas fléché. Cela signifie que le lien entre deux sommets traduit un phénomène concret où les deux sens sont possibles systématiquement et les flèches n'ont plus de sens. ,.-\' /'\ / \ / ) ,L: Dans un graphe non orienté, le couple A-B n'est plus appelé un arc mais une arête. Une chaîne est une suite de sommets. On parlait de chemins dans les graphes orientés. Un cycle est une chaîne fermée. On parlait de circuit dans les graphes orientés. *-' \ Section II - Les différentes renrésentations d'un graphe orienté Il existe différente manière de représenter un graphe orienté : o représentationsagittale, o présentationalgébrique, o matriciellebooléenne. La présentation matricielle permet d'établir deux autres représentations : o présentation par le dictionnaire des suivants, o présentation par le dictionnaire des précédents. Université de Reims - Faculté des Sciences Economiqræs, Sociales et de Gestion - Antonir Gaignette II.1 - Représentation sagittale Tout graphe peut être représenté par un ensemble de sommets reliés entre eux par des arcs fléchés. La disposition des sommets dans le plan peut être quelconque ainsi qor lu longueur des arcs. Prenons l'exemple représenté sous forme du dessin suivant : A ---------------+ B C'est ce que l'on nomme la représentation sagittale. II.2 - Présentation algebrique Fournir la présentation d'un graphe sous sa forme algébrique G : (X, Y) revient à identifier ses sommets X et ses arcs Y. Ainsi, dans l'exemple précédent: o X: (A, B, C, D, E, F) o Y: (A-B ; B-C ; B-D ; C-E ; D-E ;E-F ;F-D ; F-A) II.3 - Matrice booléenne Un graphe peut également être représenté à I'aide d'une matrice booléenne. Chaque case de la matrice est associée à un arc dans l'ordre < départ - arrivée >>. Si I'arc existe, on note ( 1 >, s'il n'existe pas, on note ( 0 >. Il est très facile à partir de cette matrice de construire le dictionnaire des suivants et le dictionnaire des précédents. \ _._ ..- _--------.---} A B C D E F A 0 I 0 0 0 0 B 0 0 I I 0 0 C 0 0 0 0 I 0 D 0 0 0 0 I 0 E 0 0 0 0 0 I F I 0 0 I 0 0 Université de Reims - Faculté des Sciences Economiques, Sociales et de Gestion - Antonin Gaignette -7- II.4 - Dictionnaire des zuivants Pour chaque sommet du graphe, le dictionnaire des suivants dresse la liste de ses suivants. Dans uploads/Management/ logistique-pert-mpm-gant-cours-de-plannification-0.pdf