th des graphe

Facult´ des sciences e D´partement de math´matiques e e Th´orie des graphes e Deuxi`mes bacheliers en sciences math´matiques e e Ann´e acad´mique 2009-2010 e e Michel Rigo Table des mati`res e Introduction 1 Chapitre I. Premier contact avec les graphes 1. Graphes orient´s e 2. Graphes non orient´s e 3. Quelques exemples 4. Chemins et circuits 4.1. Recherche du plus court chemin 4.2. Graphes et chemins eul´riens e 4.3. Connexit´ des graphes non orient´s e e 4.4. D´composition en composantes fortement connexes e 5. Sous-graphes 6. Coupes, points d'articulation, k-connexit´ e 7. Th´or`me(s) de Menger ee 8. Graphes orient´s sans circuit et tri topologique e 9. Arbres 9.1. Parcours d'arbres 10. Isomorphismes de graphes 11. Graphes hamiltoniens 11.1. Fermeture d'un graphe et th´or`me de Chv´tal ee a 5 5 8 12 22 25 29 32 33 37 38 44 46 49 51 53 56 62 Chapitre II. Un peu de th´orie alg´brique des graphes e e 1. Matrice d'adjacence 2. Th´orie de Perron-Frobenius e 2.1. P´riode d'une matrice irr´ductible e e 2.2. Estimation du nombre de chemins de longueur n 2.3. Cas d'un graphe ayant plusieurs composantes f. connexes 3. Une application : l'algorithme de PageRank 4. Alg`bre d'adjacence e 5. Arbres couvrants 5.1. Une formule de Cayley 5.2. Une preuve bijective 5.3. Nombre de sous-arbres couvrants 6. Arbres couvrants de poids minimal 69 69 73 79 83 85 87 92 95 96 98 102 108 Chapitre III. Graphes planaires 1. Introduction 111 111 i ii Chapitre . Table des mati`res e 2. Formule d'Euler 3. Graphes hom´omorphes e 4. Th´or`me de Kuratowski ee 113 115 116 Chapitre IV. Coloriage 1. Nombre chromatique 2. Le th´or`me des cinq couleurs ee 3. Polyn^me chromatique o 4. Coloriage d'ar^tes et th´or`me de Ramsey e ee 123 123 124 132 135 Chapitre V. Annexe : impl´mentation en C e 1. Pointeurs, allocation m´moire et listes cha^ ees e ?n´ 1.1. Adresses 1.2. Allocation dynamique 1.3. Structures 1.4. Listes cha^ ees ?n´ 2. Liste d'adjacence 2.1. Une manipulation simplifi´e e 2.2. Utilisation des fonctions 2.3. D´tail de l'impl´mentation e e 141 141 141 144 145 146 148 150 152 153 Bibliographie 161 Liste des figures 163 Index 169 Introduction La th´orie des graphes est, avec la combinatoire, une des pierres ane gulaires de ce qu'il est commun de d´signer par math´matiques discr`tes. e e e Cependant, elle n'a re¸u qu'assez tardivement une attention soutenue de la c part de la communaut´ math´matique. En effet, bien que les graphes eue e l´riens soient l'´manation du c´l`bre probl`me des sept ponts de K¨nigsberg e e ee e o ´tudi´ par Euler en 1736, on peut dire que les premiers d´veloppements mae e e jeurs de la th´orie des graphes datent du milieu du vingti`me si`cle (N. Biggs, e e e C. Berge, W.T. Tutte, . . . ). Ainsi, un des premiers ouvrages, si pas le premier, traitant de th´orie des graphes "Theorie der endlichen und unendlichen e Graphen" ´crit par K¨nig remonte ` 1936. Depuis cette ´poque, la th´orie e o a e e des graphes s'est largement d´velopp´e et fait ` pr´sent partie du cursus e e ae standard en math´matiques de bon nombre d'universit´s. Ces notes de cours e e constituent le support ´crit du cours dispens´ aux deuxi`mes bacheliers en e e e sciences math´matiques de l'Universit´ de Li`ge. e e e Un graphe G = (V, E ) est essentiellement d´fini par une relation binaire e E ? V × V sur un ensemble V le plus souvent fini (nous ne ferons que de br`ves incursions dans le monde des graphes infinis, ce qui sera d'ailleurs e l'occasion de donner un avant-go^ t de la th´orie des langages formels). Les u e graphes sont utilis´s pour mod´liser de nombreuses situations et leurs ape e plications sont par cons´quent aussi nombreuses que vari´es : dans d'autres e e branches des math´matiques (alg`bre, combinatoire, . . . ), en informatique, e e en recherche op´rationnelle (tourn´es de distribution, ordonnancement de e e t^ches, construction de circuits imprim´s, . . . ), en cartographie (coloriage a e de cartes), en chimie, etc . . . . Selon nous, il est impensable de vouloir traiter efficacement un probl`me e r´el (i.e., de taille non n´gligeable) sans poss´der de solides bases. Ainsi, nos e e e d´veloppements seront principalement th´oriques. N´anmoins, le caract`re e e e e appliqu´ de la th´orie sera mis en exergue par de nombreux exemples (en e e particulier, au premier chapitre, nous d´taillons une s´rie de probl`mes issus e e e du "monde r´el".) e Par essence, en math´matiques discr`tes et a fortiori en th´orie des e e e graphes, de nombreux raisonnements ont une composante combinatoire importante. Ainsi, des preuves pouvant ^tre jug´es "difficiles" consistent soue e vent en une succession, parfois longue, de raisonnements simples (mais pas toujours ais´s ` saisir). D`s lors, certaines parties para^ ea e ?tront peut-^tre come plexes sans pour autant ^tre compliqu´es ! Nous esp´rons que des exemples e e e 1 2 Chapitre . Introduction bien choisis pourront alors aider le lecteur dans sa compr´hension. Bien e ´videmment, les m´thodes mises ici en ´vidence sont souvent tout autre e e e que celles des "math´matiques du continu" comme l'analyse. Nous esp´rons e e que cette pr´sentation permettra ainsi ` l'´tudiant d'enrichir sa palette de e ae techniques et de raisonnements math´matiques. (Les math´matiques ne e e sont bien s^ r pas cloisonn´es et les interactions entre les diverses branches u e sont nombreuses et souvent fort riches: "It is unquestionable that interplay between ideas from different sources, and elaborate techniques successfully applied, are among the features that make much of mathematics fascinating. Moreover, mathematics does often display a tendency to unify itself and to build up a body of technique. Therefore one may well guess that graph theory, as it matures, will continue to develop its own characteristic techniques and that many of its results will become increasingly unified, both among themselves and with the rest of mathematics."1.) Dans le premier chapitre, nous pr´sentons la notion de graphe et ses e variantes (graphe non orient´, arbre, multi-graphe, hypergraphe). Les prine cipaux r´sultats du chapitre concernent les graphes eul´riens et les graphes e e hamiltoniens (th´or`me de Dirac, d'Ore et de Chv´tal). ee a Le deuxi`me chapitre donne quelques r´sultats de la th´orie alg´brique e e e e des graphes. En effet, ` un graphe G, on associe de mani`re classique une a e matrice, appel´e matrice d'adjacence. D`s lors, l'application de r´sultats e e e standards d'alg`bre lin´aire permet de d´duire des renseignements non trie e e viaux sur G. Par exemple, on d´nombre le nombre d'arbres couvrants d'un e graphe donn´ par un simple calcul de mineur. Nous pr´sentons ´galement e e e quelques ´l´ments concernant la th´orie de Perron-Frobenius qui permet une ee e estimation assez fine du nombre de chemins de longueur n dans un graphe. Les trois chapitres suivants sont assez classiques. Les th`mes ´voqu´s e e e sont pr´sent´s dans bon nombre d'ouvrages d'introduction ` la th´orie des e e a e graphes. On y ´tudie les graphes planaires, i.e., les graphes pouvant ^tre e e repr´sent´s dans le plan euclidien par une figure dont les arcs ne se coupent e e pas. Ensuite, on s'int´resse ` quelques probl`mes de coloriage (th´or`me e a e ee des quatre/cinq couleurs) et en particulier, ` l'important th´or`me de Rama ee sey qui permet d'introduire sommairement la th´orie extr´male des graphes. e e Enfin, suivant le temps disponible, quelques heures du cours seront consacr´es ` pr´senter l'un ou l'autre probl`mes "d'actualit´" de recherche en eae e e math´matiques discr`tes. e e Vu le caract`re appliqu´ indubitable du sujet, le dernier chapitre est une e e annexe pr´sentant une impl´mentation en langage C des graphes finis (oriene e t´s) par liste d'adjacence. Cette structure de donn´es est particuli`rement e e e bien adapt´e aux graphes peu denses. En effet, tout au long du pr´sent e e texte, divers algorithmes sont pr´sent´s sous forme de pseudo-code. Il est e e donc indispensable de disposer d'une interface raisonnable pour impl´menter e 1C. ST. J. A. Nash-Williams, dans la pr´face de [3]. e 3 et tester ces algorithmes sur des jeux de donn´es cons´quents. Signalons que e e de nombreux probl`mes rencontr´s en th´orie des graphes sont, du point e e e de vue de la complexit´, difficiles. Cependant, nous avons volontairement e omis les notions de complexit´ algorithmique et de calculabilit´ : probl`mes e e e NP, NP-difficiles ou NP-complets. (Cette probl´matique est pr´sent´e en e e e troisi`me ann´e de bacheliers en sciences math´matiques.) e e e Une fois n'est pas cout^ me, je voudrais aussi remercier (et les futurs ´tudiu e ants ayant ces notes de cours entre les mains s'associeront certainement ` moi) a l'ensemble des ´tudiants de deuxi`me bachelier de l'ann´e acad´mique 2005-2006 e e e e et en particulier : C´dric H., Damien G., Damien K., Damien L., Kastriot, Marie, e Mehdi, M´lissa, Na¨ Nicolas, Rukiye, . . . . Leur int´r^t marqu´, leurs questions e ?m, ee e pertinentes, leurs interrogations m'ont permis d'am´liorer (et parfois de corriger) la e pr´sentation de ce cours. Je n'oublierai pas non plus les retours et les suggestions e de Laurent Waxweiler. CHAPITRE I Premier contact avec les graphes Un petit dessin vaut mieux qu'un grand discours, Napol´on. e Introduire une nouvelle mati`re n'est pas toujours chose plaisante car il e s'agit souvent d'une accumulation de d´finitions ! Et c'est h´l`s la situation e ea rencontr´e ici. Nous allons donc agr´menter cette pr´sentation, autant que e e e faire se peut, d'exemples mettant en lumi`re l'int´r^t pratique de la th´orie e ee e des graphes. Comme l'indique le titre de ce chapitre, nous nous int´ressons e aux graphes et comme le lecteur va tr`s vite s'en apercevoir, il en existe de e plusieurs types: simple, multi-graphe, digraphe, hyper-graphe,. . . 1. Graphes orient´s e D´finition I.1.1. Soient V un ensemble (fini ou infini) et E une partie de e V × V (i.e., une relation sur V ). Le graphe G = (V, E ) est la donn´e du e couple (V, E ). Les ´l´ments de V sont appel´s les sommets1 ou noeuds de ee e G. Les ´l´ments de E sont appel´s les arcs2 ou ar^tes de G. Si V est fini, ee e e on parlera de graphe fini (en particulier, E est alors fini et contient au plus (#V )2 arcs). Remarque I.1.2. Observons que l'ordre au sein des couples appartenant a ` E est intrins`quement pr´sent3. On parlera donc parfois de graphe orient´ e e e ou de graphe dirig´. Soit I , un ensemble d'indices. Si V = {vi i ? I } et si e a = (vi , vj ), i, j ? I , on pourra alors parler de l'origine vi et de la destination vj de l'arc a. On dit que vi et vj sont les extr´mit´s de l'arc a et que a relie ee vi ` vj . Si b = (vi , vi ), on parle g´n´ralement de la boucle b. Il est souvent a ee commode de donner une repr´sentation sagittale d'un graphe. Les sommets e 1En anglais, cela se dit "vertex" (au pluriel, "vertices"). D'o` l'initiale V pour d´signer u e l'ensemble des sommets. Dans ces notes, nous ne d´rogerons pas ` la coutume angloe a saxonne de noter un graphe G = (V, E ). 2En anglais, cela se dit "edge". D'o` l'initiale usuelle E . u 3On parle de couple et non de paire. Un couple est une paire ordonn´e. On distingue e d'ailleurs les notations (x, y ) et {x, y }. 5 Cette distinction va devenir rapidement indispensable, lorsqu'on introduira les graphes non orient´s. e 6 arcs adjacents Chapitre I. Premier contact avec les graphes sont repr´sent´s par des points et si (vi , vj ) est un arc, alors on trace une e e fl`che de vi vers vj (cf. figure I.1). Deux arcs sont adjacents s'ils ont au e moins une extr´mit´ en commun. ee vi vj vi = vj Figure I.1. Un arc reliant deux sommets, une boucle. arc incident a un sommet ` D´finition I.1.3. Soit a = (vi , vj ) ? E . On dit que a est un arc sortant e de vi ou encore que a est un arc incident ` vi vers l'ext´rieur (resp. un arc a e entrant dans vj ou encore que a est un arc incident ` vj vers l'int´rieur). a e L'ensemble des arcs sortant de vi est not´ ? + (vi ) et l'ensemble des arcs e entrant dans vj est not´ ? - (vj ). L'ensemble des arcs incidents ` un sommet e a + (v ) ? ? - (v ). On d´finit le demi-degr´ sortant (resp. demiv est ? (v ) := ? e e degr´ entrant) d'un sommet v par e d+ (v ) = #(? + (v )) Handshaking formula. (resp. d- (v ) = #(? - (v ))). Si G = (V, E ) est un graphe fini, il est clair que d- (v ). d+ (v ) = v?V v?V d+ (v ) + d- (v ). Enfin, le degr´ de v est deg(v ) = e L'ensemble des successeurs d'un sommet v est l'ensemble succ(v ) = {s1 , . . . , sk } des sommets si tels que (v, si ) ? ? + (v ), i.e., (v, si ) ? E . De mani`re analogue, l'ensemble e des pr´d´cesseurs d'un sommet v est l'ensemble pred(v ) = {s1 , . . . , sk } des ee sommets si tels que (si , v ) ? ? - (v ), i.e., (si , v ) ? E . Enfin, l'ensemble des voisins de v est simplement ? (v ) = pred(v ) ? succ(v ). sommets adjacents Si u appartient ` ? (v ), on dit que u et v sont des sommets voisins ou adjaa cents. u Exemple I.1.4. Soit le graphe G = (V, E ) o` V = {a, b, c, d, e} et E = {(a, b), (a, e), (b, b), (b, c), (c, c), (c, d), (c, e), (d, a), (e, a), (e, d)}. Celui-ci est repr´sent´ ` la figure I.2. Par exemple, ? + (a) = {(a, b), (a, e)} e ea a b c e d Figure I.2. Un exemple de graphe. I.1. Graphes orient´s e 7 et ? - (d) = {(c, d), (e, d)}. On a aussi succ(a) = {b, e}, succ(b) = {b, c}, pred(d) = {c, e} et ? (a) = {b, d, e}. On voit aussi que les arcs (e, a) et (d, a) sont adjacents. Enfin, le demi-degr´ sortant de c est d+ (c) = 3. e D´finition I.1.5. Un multi-ensemble4 est un ensemble au sein duquel un e m^me ´l´ment peut ^tre r´p´t´ plus d'une fois. Ainsi, on s'int´resse non e ee e e ee e seulement ` savoir si un ´l´ment appartient ou non ` un multi-ensemble a ee a donn´, mais ´galement ` sa multiplicit´. Par exemple, {1, 1, 2, 3}, {1, 2, 3} e e a e et {1, 2, 2, 3} sont des multi-ensembles distincts. Pour distinguer les copies d'un m^me ´l´ment x, il est commode de les indicer. Par exemple, on consie ee d`re le multi-ensemble {11 , 12 , 13 , 21 , 22 , 3}. Cette mani`re de proc´der nous e e e permettra de d´finir facilement des fonctions d´finies sur un multi-ensemble. e e Un multi-graphe G = (V, E ) est un graphe pour lequel l'ensemble E des arcs est un multi-ensemble. Autrement dit, il peut exister plus d'un arc reliant deux sommets donn´s. Un exemple de repr´sentation d'un multie e graphe est donn´ ` la figure I.3. Un multi-graphe G = (V, E ) est fini si V ea a b c e d Figure I.3. Un exemple de multi-graphe. et E sont finis. (En effet, dans le cas des multi-graphes, supposer V fini n'implique pas que E soit fini.) Soit p >= 1. Un p-graphe est un multi-graphe G = (V, E ) pour lequel tout arc de E est r´p´t´ au plus p fois. En particulier, un 1-graphe est un e ee graphe. e Remarque I.1.6. On peut observer que la remarque I.1.2, la d´finition I.1.3 et la "handshaking formula" s'appliquent ´galement au cas des multie graphes. Il est laiss´ au lecteur le soin d'adapter les d´finitions de ? + (v ), e e + (v ), succ(v ) et ? - (v ), d- (v ), pred(v ). En particulier, ? + (v ) et ? - (v ) sont d en g´n´ral des multi-ensembles. ee D´finition I.1.7. Un graphe G = (V, E ) est dit simple (ou strict) s'il ne e s'agit pas d'un multi-graphe et si E est irr´flexif, c'est-`-dire que quel que e a soit v ? V , (v, v ) n'appartient pas ` E (i.e., G ne contient pas de boucle). a Un exemple de graphe simple est donn´ ` la figure I.4. ea 4Cette d´finition n'est pas tr`s rigoureuse. En effet, le concept m^me d'ensemble ne e e e vous a, jusqu'` pr´sent, ´t´ introduit que de mani`re na¨ ae ee e ?ve. On suppose qu'un ´l´ment ee est r´p´t´ au plus un nome ee bre d´nombrable de fois. e 8 Chapitre I. Premier contact avec les graphes a b c e d Figure I.4. Un exemple de graphe simple. 2. Graphes non orient´s e Les graphes non orient´s sont en fait un cas particulier de graphes (orie ent´s). e D´finition I.2.1. Soit G = (V, E ) un graphe (resp. un multi-graphe). Si e E est une relation sym´trique sur V , on dira que G est un graphe (resp. un e multi-graphe) non dirig´ ou non orient´. Autrement dit, G est non dirig´ si e e e ?v1 , v2 ? V : (v1 , v2 ) ? E => (v2 , v1 ) ? E. Dans ce cas, on simplifie la repr´sentation sagittale de G en tra¸ant simplee c ment un segment entre v1 et v2 . Pour all´ger l'´criture, on identifiera les e e arcs (vi , vj ) et (vi , vj ) avec une unique "ar^te non orient´e" donn´e par la e e e paire {vi , vj }. Dans le cas dirig´ (resp. non dirig´), nous nous efforcerons e e de parler d'arcs (resp. d'ar^tes). e Si par contre, on d´sire insister sur le caract`re non sym´trique de E , on e e e 5 parlera de graphe dirig´ ou, par abus de langage, digraphe . e Les d´finitions rencontr´es pr´c´demment s'adaptent ais´ment au cas e e ee e non orient´. e ar^te incidente e a un sommet ` ar^tes adjacentes e sommets adjacents e D´finition I.2.2. Soient G = (V, E ), un multi-graphe non orient´ et a = e {vi , vj } une de ses ar^tes. On dit que a est incident aux sommets vi et vj . Le e nombre d'ar^tes incidentes ` vi est le degr´ de vi , not´ deg(vi ). On suppose e a e e en outre que les boucles apportent une double contribution au degr´ d'un e sommet. L'ensemble des ar^tes incidentes ` vi se note ? (vi ). Il est clair e a que, dans un graphe simple, deg(vi ) = #(? (vi )). Ces notations sont bien ´videmment compatibles avec celles donn´es dans le cas orient´. Deux ar^tes e e e e sont adjacentes si elles ont au moins une extr´mit´ en commun. ee Deux sommets vi , vj ? V sont adjacents si l'ar^te {vi , vj } appartient ` e a E . On dit aussi qu'ils sont voisins. L'ensemble des voisins de v se note ? (v ). Enfin, la d´finition d'un p-graphe est analogue ` celle donn´e dans le cas e a e orient´. e Remarque I.2.3 (Handshaking lemma). Si G = (V, E ) est un multigraphe non orient´, alors e deg(v ) = 2 #E. v?V 5En anglais "directed graph" se contracte en "digraph". I.2. Graphes non orient´s e 9 C'est imm´diat. (Et on comprend mieux la double contribution des boucles e pour le degr´ d'un sommet. . . .) e L'exemple suivant illustre les diff´rentes classes de graphes rencontr´es e e jusqu'` pr´sent. Bien s^ r, tout graphe simple est un graphe et tout graphe ae u est un multi-graphe. Exemple I.2.4. A la figure I.5, on a repr´sent´, dans le cas dirig´, un e e e graphe simple, un graphe et enfin, un multi-graphe. La figure I.6 reprend Figure I.5. Un graphe (dirig´) simple, un graphe et un e multi-graphe. les m^mes ´l´ments dans le cas non orient´. e ee e Figure I.6. Un graphe (non dirig´) simple, un graphe et un e multi-graphe. e e D´finition I.2.5. Soit k >= 1. Un multi-graphe orient´ (resp. non orient´) e G = (V, E ) est k-r´gulier si pour tout v ? V , d+ (v ) = k (resp. deg(v ) = k). e Le graphe de gauche (resp. de droite) de la figure I.7 est 3-r´gulier (resp. e 4-r´gulier). Le graphe de droite de la figure I.7 est en particulier simple et e Figure I.7. Des graphes non orient´s 3 et 4-r´guliers. e e complet. Un graphe G = (V, E ) est complet si E = V × V , plus exactement, on suppose souvent que E = V × V \ {(v, v ) v ? V } (autrement dit, on ne tient pas compte des boucles). En particulier, un graphe complet est sym´trique. On note Kn le graphe simple non orient´ e e 10 Chapitre I. Premier contact avec les graphes Figure I.8. Un multi-graphe orient´ 2-r´gulier. e e complet ` n sommets. Ainsi, la figure I.7 repr´sente le graphe K5 . Dans a e ce cours, lorsqu'on parlera de graphes complets, il sera sous-entendu qu'il s'agit de graphes simples et non orient´s. e e D´finition I.2.6. Un graphe G = (V, E ) est dit biparti si V peut ^tre e partitionn´ en deux ensembles V1 et V2 de mani`re telle que E ? V1 × V2 . e e Si #V1 = m, #V2 = n et E = V1 × V2 , alors on parle du graphe biparti V 1 V 2 Figure I.9. Un graphe biparti (non complet). complet et il est not´ Km,n . On peut g´n´raliser cette notion et d´finir des e ee e graphes n-partis, pour n >= 2. Pour ce faire, V doit ^tre partitionn´ en n e e sous-ensembles V1 , . . . , Vn de mani`re telle que e E? Vi × Vj . i=j D´finition I.2.7. Un multi-graphe G = (V, E ) (orient´ ou non) est ´tiquet´ e e e e (par f ) s'il existe une fonction f :E->? o` ? est un ensemble quelconque. Si ? ? R+ = [0, +?[, on parle souvent u de multi-graphe pond´r´ et on dit que f est une fonction de poids. Un ee ´tiquetage peut par exemple servir ` pr´ciser des co^ ts (co^ t de transport, e ae u u des distances, des couleurs, etc. . . ). Si a est un arc, f (a) est l'´tiquette, e le label ou encore le poids de a. On peut de la m^me mani`re d´finir un e e e ´tiquetage des sommets au moyen d'une fonction g : V -> ?. e e Exemple I.2.8. Le graphe de la figure I.10 repr´sente quelques villes belges connect´es par un r´seau autoroutier. L'´tiquette de chaque ar^te repr´sente e e e e e la distance, par autoroute, entre les deux extr´mit´s de celle-ci. Nous avons ee choisi un graphe non orient´ car les autoroutes belges vont toujours dans les e deux sens. I.2. Graphes non orient´s e Bruges 11 Anvers 107 98 121 Bxl. 131 97 Liège 70 65 76 Namur Mons 131 143 207 Arlon Figure I.10. Graphe ´tiquet´ par les distances entre villes e e (itin´raire "express" calcul´ par www.mappy.fr). e e Pour terminer cette section, nous g´n´ralisons le concept de graphe en ee autorisant non plus des relations binaires entre sommets (autrement dit, des arcs) mais des relations d'arit´ quelconque (des hyper-ar^tes). Ensuite, nous e e donnons une br`ve introduction aux matro¨ e ?des. e D´finition I.2.9. Un hyper-graphe H = (V, E ) est la donn´e de deux e ensembles V et E . L'ensemble V , comme dans le cas d'un graphe, est l'ensemble des sommets de H . Par contre, E est une partie de P (V ) (l'ensemble des parties de V ). Un ´l´ment de E est appel´ hyper-ar^te. ee e e Soient V = {a, b, c, d, e} et E = {{a, b}, {a, c, d}, {b, d, e}}. On dispose de l'hyper-graphe H = (V, E ) repr´sent´ ` la figure I.11. Un e ea c a d b e Figure I.11. Un exemple d'hyper-graphe. hyper-graphe H = (V, E ) est fini si V est fini. La notion de matro¨ est d^ e ` H. Whitney (1935) et a ´t´ d´velopp´e ?de ua ee e e par W. Tutte. Elle permet notamment l'´tude axiomatique des propri´t´s e ee de l'ind´pendance lin´aire ou aussi l'´tude des cycles et des arbres. e e e D´finition I.2.10. Un matro¨de (M, I ) est la donn´e d'un ensemble fini e ? e M et d'une partie I de P (M ), i.e., d'une collection de sous-ensembles de M , v´rifiant les trois propri´t´s suivantes e ee 12 Chapitre I. Premier contact avec les graphes ? ? ? ? ? I (de mani`re ´quvalente, I est non vide), ee si X ? I et Y ? X , alors Y ? I , si X, Y ? I et #X > #Y , alors il existe x ? X \ Y tel que Y ? {x} ? I . Les ensembles de I sont dits ind´pendants. Enfin, un matro¨ est qualifi´ e ?de e de normal si tous les singletons sont ind´pendants. e Exemple I.2.11. Soient E un espace vectoriel, M une partie finie de E et I la collection des parties libres de M . Le couple (M, I ) est un matro¨ ?de. Exemple I.2.12. Soit G = (V, E ) un graphe non orient´ simple. On e consid`re le matro¨ (E, I ) o` une partie X de E appartient ` I si et e ?de u a seulement si X ne contient aucun cycle (i.e., X est une for^t). e Remarque I.2.13. Tout matro¨ (M, I ) est bien ´videmment un hyper?de e graphe. Les sommets de ce dernier sont les ´l´ments de M et les hyper-ar^tes ee e sont les ´l´ments de I . ee 3. Quelques exemples Nous allons pr´senter dans cette courte section quelques exemples de e graphes permettant la mod´lisation de divers probl`mes. Puisqu'il ne s'agit e e que d'exemples, certaines d´finitions sont volontairement omises. Elles seront e pr´cis´es en temps utiles. Nous esp´rons que la vari´t´ des exemples pr´senee e ee e t´s servira de motivation profonde ` l'´tude th´orique r´alis´e dans les sece ae e ee tions et chapitres suivants. Pour des raisons ´videntes de pr´sentation, nous e e ne donnons que des exemples de "petite taille" qui peuvent souvent ^tre r´e e solus sans v´ritable m´thode. Dans des probl`mes r´els, il faut imaginer des e e e e graphes pouvant avoir plus de 106 sommets. Dans ce cas, la solution para^ ?t nettement moins ´vidente ! e e e Exemple I.3.1 (Circuit eul´rien). Les ouvrages de th´orie des graphes reprennent toujours le c´l`bre exemple des ponts de K¨nigsberg. Nous ne ee o d´rogerons pas ` cette r`gle. Au XVII-i`me si`cle, les habitants de K¨nigse a e e e o berg (actuel Kaliningrad, ville de Russie proche de la Lituanie et de la Pologne o` coule la rivi`re Pregel) d´siraient se promener le dimanche en u e e passant une et une seule fois par chacun des sept ponts de la ville. Les ponts ´taient dispos´s comme ` la figure I.12. Une mod´lisation du probl`me ree e a e e vient ` consid´rer un graphe ayant comme sommets, les deux rives et les a e deux ^ et comme ar^tes, les sept ponts. Puisqu'il n'y a aucune contrainte ?les e sur le sens de parcours des ponts, nous avons choisi un multi-graphe non orient´. e La question g´n´rale sous-jacente est donc de d´terminer pour un multiee e graphe donn´ (´ventuellement orient´) s'il existe un circuit, i.e., un chemin ee e ferm´, passant une et une seule fois par chaque ar^te. e e e Exemple I.3.2 (Circuit hamiltonien -- TSP). Le probl`me du voyageur de commerce (Travel Salesman Problem) est en quelque sorte un "probl`me e I.3. Quelques exemples 13 Figure I.12. Les sept ponts de K¨nigsberg. o dual" de l'exemple pr´c´dent (on s'int´resse ici ` trouver un circuit passant ee e a une et une seule fois par chaque sommet et non par chaque ar^te). On e cherche un circuit permettant non seulement de relier n villes en passant une et une seule fois par chacune d'entre elles, mais de plus, ce circuit doit minimiser la distance totale parcourue. On pourrait par exemple consid´rer e les villes belges et les donn´es de la figure I.10 et en d´terminer un circuit e e optimal. Dans certains cas, on a recours ` un graphe orient´ plut^t qu'` a e o a un graphe non orient´ comme ` la figure I.10. Cela a pour avantage de e a permettre la mod´lisation de co^ ts diff´rents pour aller d'un sommet A ` e u e a un sommet B plut^t que de B ` A (ceci permet, par exemple, de prendre o a en compte des sens uniques, des payages, des temps de transports diff´rents e suivant la direction choisie, etc. . . ). Il s'agit donc de probl`mes typiques rencontr´s dans la d´termination de e e e tourn´es, de circuits de distribution, etc. . . e e Exemple I.3.3 (Coloriage). Consid´rons un cube. Si chaque sommet (resp. chaque ar^te) d'un graphe repr´sente un sommet (resp. une ar^te) du e e e cube, on obtient le graphe de gauche de la figure I.13, on parle du squelette du cube. Par contre, si on repr´sente les faces du cube par les sommets d'un e graphe et si les sommets du graphe correspondant ` des faces du cube ayant a une ar^te commune sont adjacents, on obtient celui de droite. On peut alors e B R R V B R B B R B R V R B Figure I.13. Deux repr´sentations d'un cube. e poser la question g´n´rale de d´terminer le nombre de couleurs n´cessaire ee e e et suffisant pour colorier les sommets d'un multi-graphe donn´, de mani`re e e telle que deux sommets adjacents ne re¸oivent pas la m^me couleur. Si on c e 14 Chapitre I. Premier contact avec les graphes r´pond ` cette question dans le cas de notre exemple initial, on s'aper¸oit e a c que pour colorier les sommets (resp. les faces d'un cube), deux (resp. trois) couleurs sont suffisantes. Exemple I.3.4 (Cartographie). Quel est le nombre minimum de couleurs n´cessaires pour colorier les pays d'une carte6 g´ographique de mani`re telle e e e que des couleurs distinctes soient attribu´es ` des pays voisins ? Ce probl`me ea e Figure I.14. La carte des USA. se ram`ne au pr´c´dent. On consid`re un graphe ayant pour sommet les e ee e diff´rents pays de la carte. Deux sommets sont adjacents si et seulement si e ils partagent une fronti`re. e e Exemple I.3.5 (Graphe d'incompatibilit´). Pour le transport de produits chimiques par rail, certains de ces produits ne peuvent ^tre transport´s dans e e un m^me wagon (des produits co-combustibles sont plac´s dans des wagons e e distincts). La figure I.15 repr´sente le graphe d'incompatibilit´ de transport e e (deux sommets adjacents ne peuvent ^tre plac´s dans le m^me wagon). On e e e P 1 P2 P 4 P3 P5 P6 Figure I.15. Graphe d'incompatibilit´. e Par rapport a l'exemple ` pr´c´dent, ee le graphe n'est pas n´cessairement e planaire. demande de minimiser le nombre de wagons n´cessaires au transport. Ce e probl`me se ram`ne donc ` un probl`me de coloriage. Deux sommets adjae e a e cents doivent avoir des couleurs distinctes, une couleur correspondant ` un a wagon. 6La figure I.14 est tir´e de http://www.math.gatech.edu/~thomas/FC/fourcolor.html e I.3. Quelques exemples 15 Exemple I.3.6 (Coloriage d'ar^tes). Au lieu de vouloir colorier les some mets d'un multi-graphe, on peut aussi s'int´resser au probl`me suivant. e e D´terminer le nombre de couleurs n´cessaires et suffisantes pour colorier e e les ar^tes d'un multi-graphe donn´, de mani`re telle que deux ar^tes adjae e e e centes ne re¸oivent pas la m^me couleur. c e Exemple I.3.7 (Graphe de Cayley). Soit G un groupe et S un ensemble de g´n´rateurs de G (tout ´l´ment de G s'obtient comme produit d'un nombre ee ee fini d'´l´ments de S ou d'inverses d'´l´ments de S ). Le graphe de Cayley ee ee du groupe G (par rapport ` S ) est un graphe orient´ CS (G) ayant pour a e sommets les ´l´ments de G. Ses arcs sont d´finis comme suit. Pour tous ee e g ? G, s ? S , l'arc (g, gs) est un arc du graphe ayant s pour label. Soit le groupe sym´trique S3 des permutations ` 3 ´l´ments ayant pour ensemble e a ee g´n´rateur7 ee S = {x = 1 2 , y = 1 3 , z = 2 3 }. Il est clair que xx = yy = zz = id, xz = 1 2 xy = 1 2 2 3=1 2 3, 1 3=1 3 2, yz = 1 3 23=132 et yx = 1 2 3 , zx = 1 3 2 , zy = 1 2 3 . Le graphe de Cayley correspondant est repr´sent´ ` la figure I.16. e ea id y x x z y z x y (1 2 3) y z (1 3 2) x z Figure I.16. Graphe de Cayley de S3 . On peut obtenir un autre graphe de Cayley de S3 en consid´rant comme e ensemble de g´n´rateurs {a = 1 2 3 , b = 1 2 }. On obtient alors le ee graphe de la figure I.17 (les d´tails de calcul sont laiss´s au lecteur). Bien e e ´videmment, le graphe de Cayley d'un groupe ne donne aucun renseignement e qui ne saurait ^tre obtenu sous une forme "alg´brique" classique. N´anmoins, e e e un tel diagramme a l'avantage de fournir presque imm´diatement certaines e informations qui seraient plus p´nibles ` obtenir par d'autres moyens (imagie a nez un groupe d´fini par certaines relations, par exemple, cd = dc, c2 dc = d, e etc. . . ). Ainsi, il est ici imm´diat de v´rifier sur la figure I.17 que les ´l´ments e e ee 7Rappelez-vous, toute permutation est un produit de transpositions. 16 Chapitre I. Premier contact avec les graphes a2 b ba a a a a b a b id a ba2 b a Figure I.17. Un autre graphe de Cayley de S3 . baaba et a2 sont identiques (il suffit de suivre les labels de chemins depuis id). L'utilisation des graphes de Cayley se r´v`le ^tre un outil souvent bien ee e utile en th´orie des repr´sentations ou dans la r´solution de probl`mes pr´cis e e e e e a ` l'aide de l'ordinateur. ee ee a Exemple I.3.8 (Arbre couvrant). Une soci´t´ de t´l´phonie souhaite c^bler enti`rement, au moyen de nouvelles fibres optiques, une ville en minimisant e le nombre de connexions ` r´aliser. Le nouveau cablage s'appuie sur le r´seau ae e ´lectrique d´j` existant et bien ´videmment, tous les points de la ville doivent e ea e ^tre d´servis. La figure I.20 repr´sente le r´seau actuel de la ville et ses cone e e e nexions. A droite, se trouve les s´lections envisag´es. La question g´n´rale e e ee Figure I.18. Sous-graphe couvrant. qui est pos´e est de rechercher un sous-graphe (ou un sous-arbre) couvrant e dans un graphe donn´. On peut aussi envisager une version pond´r´e dans e ee laquelle chaque arc aurait un co^ t et on rechercherait un sous-graphe (ou un u sous-arbre) couvrant de poids minimal. e a e Exemple I.3.9 (Forte connexit´). Suite ` divers probl`mes de circulation, des responsables communaux d´sirent placer les rues d'un quartier ` sens e a unique. Si un graphe mod´lise les rues et leurs croisements, la question qui e se pose est donc d'orienter les arcs d'un graphe non orient´ de mani`re telle e e I.3. Quelques exemples 17 qu'il existe un chemin orient´ entre toute paire de sommets. Un tel exemple e est donn´ ` la figure I.19. ea Figure I.19. Orientation d'un graphe. e e Exemple I.3.10 (Distance). Consid´rons le probl`me de routage de paquets de donn´es devant transiter sur un r´seau (du type internet). Si un e e utilisateur d´sire acc´der au contenu d'une page web pr´sente sur un serveur, e e e une connexion entre ce serveur et la machine doit ^tre ´tablie. Cette cone e nexion n'est en g´n´ral pas directe mais doit passer par une s´rie de maee e chines relais. Pour pr´server la bande passante, pour acc´l´rer le transfert e ee ou encore pour minimiser les co^ ts, on essaie de minimiser le nombre de u "hops" (i.e., le nombre de machines relais utilis´es). Si chaque ordinateur, e routeur, passerelle ou serveur pr´sents sur l'internet repr´sente un sommet e e d'un graphe dont les arcs repr´sentent les connexions entre ceux-ci, il s'agit e d'un probl`me d´licat! Voici un exemple de "route" suivie par un paquet de e e donn´es : e > traceroute www.google.be traceroute to www.google.be (66.249.85.99), 30 hops max, 40 byte packets 1 mont3-0014.gw.ulg.ac.be (139.165.159.1) 0.177 ms 0.177 ms 0.163 ms 2 segi3-0813-mont3.gw.ulg.ac.be (193.190.228.125) 0.221 ms 0.179 ms 0.184 ms 3 inet3-3031.gw.ulg.ac.be (139.165.192.49) 0.734 ms 0.612 ms 0.597 ms 4 fe.m20.access.liege.belnet.net (193.191.10.17) 0.791 ms 0.707 ms 0.713 ms 5 oc48.m160.core.science.belnet.net (193.191.1.185) 2.266 ms 2.239 ms 16.679 ms 6 oc192.m160.ext.science.belnet.net (193.191.1.2) 2.252 ms 2.260 ms 2.235 ms 7 216.239.43.88 7.954 ms 7.922 ms 7.731 ms 8 64.233.175.249 14.932 ms 14.906 ms 14.911 ms 9 216.239.46.49 14.628 ms 14.431 ms 14.407 ms 10 66.249.85.99 14.409 ms 14.722 ms 14.624 ms Le probl`me g´n´ral sous-jacent est donc de d´terminer, dans un graphe e ee e donn´, le chemin le plus court permettant de relier deux sommets quelconques e d'un graphe. On pourra envisager des variantes pond´r´es ou orient´es. Dans ee e la version pond´r´e, on recherchera le chemin de poids minimal. ee e e e Exemple I.3.11 (Planarit´). Lors de l'´laboration de circuits ´lectriques, les connexions reliant les diff´rents composants ne peuvent se toucher sous e peine de court-circuit. La question de th´orie des graphes qui est pos´e est e e donc de d´terminer si, dans le plan, il existe une configuration g´om´trique e ee des sommets et des arcs du graphe assurant qu'aucune paire d'arcs ne se 18 Chapitre I. Premier contact avec les graphes Figure I.20. Un graphe planaire. croise. Si tel est le cas, on parle de graphe planaire. Plut^t que de repr´senter o e un graphe dans un plan, on pourrait aussi imaginer des repr´sentations sur e une sph`re ou un tore et se poser la m^me question. Ainsi, le graphe K3,3 de e e la figure I.21 n'est pas planaire (cf. Lemme III.4.2), mais si on le repr´sente e sur un tore, on peut obtenir une repr´sentation dont les arcs ne se coupent e pas (cf. figure I.22). Notons enfin que, dans l'´laboration des circuits e Figure I.21. Un graphe non planaire. 11 00 1 0 11 00 11 1 00 0 11 1 00 0 11 00 11 1 00 0 11 00 Figure I.22. K3,3 sur un tore. imprim´s (VLSI8 par exemple), il est possible de r´aliser de tels circuits sur e e plusieurs couches. Ainsi, un autre probl`me serait de d´terminer le nombre e e minimum de couches ` envisager pour la conception du circuit imprim´. a e Remarque I.3.12. Le graphe de la figure I.21 est classiquement illustr´ e par le probl`me des trois villas et des trois usines. Imaginez que trois vile las doivent ^tre reli´es au gaz, ` l'eau et ` l'´lectricit´. Est-il possible de e e a ae e construire des canalisations alimentant chaque villa depuis chaque usine de mani`re telle que ces canalisations ne se chevauchent pas ? e e Exemple I.3.13 (Graphe d'intervalles). Consid´rons les intervalles ouverts ]0, 2[, ]1, 4[, ]2, 5[, ]3, 4[, ]3, 8[ et ]6, 8[. A chaque intervalle correspond un sommet d'un graphe non orient´. Si ]a, b[?]c, d[= ?, alors une ar^te relie e e dans le graphe les sommets correspondant ` ces deux intervalles. Le graphe a 8Very Large Scale Integration I.3. Quelques exemples 19 d'intervalles correspondant aux intervalles donn´s ci-dessus est repr´sent´ ` e e ea la figure I.23. Ces graphes sont parfois utilis´s en arch´ologie ou encore en e e ]3,4[ 0 1 2 3 4 5 6 8 ]2,5[ ]1,4[ ]3,8[ ]6,8[ ]0,2[ Figure I.23. Graphe d'intervalles. g´n´tique pour exprimer ou mettre en ´vidence des ´l´ments communs se ee e ee produisant ` travers le temps (par exemple, des caract´ristiques communes a e d'une p´riode de l'histoire ou des mutations g´n´tiques au sein du g´nome). e ee e e Exemple I.3.14 (Probl`me d'affectation). Soient O1 , . . . , Ok des ouvriers et T1 , . . . , Tt des postes de travail. Chaque ouvrier Oi poss`de certaines e qualifications lui permettant de travailler sur certains postes Ti,1 , . . . , Ti,di . Comment r´partir les ouvriers pour que chaque poste de travail soit occup´ e e par au moins un ouvrier ? Pour mod´liser ce probl`me, on utilise un graphe e e biparti dont les sommets repr´sentent les ouvriers et les postes. On trace un e arc entre Oi et Tj si Oi poss`de la qualification pour travailler au poste Tj . e O1 O2 O3 O4 T1 T2 T3 T4 Figure I.24. Probl`me d'affectation. e Exemple I.3.15 (Tri topologique). Dans la majorit´ des exemples d´crits e e pr´c´demment, nous avons rencontr´ des graphes non orient´s. Un exemple ee e e de graphe orient´ est le suivant. On rencontre parfois des probl`mes pour e e lesquels on recherche un ordre acceptable dans l'ordonnancement de t^ches a d´pendant les unes des autres. On peut par exemple penser ` la fabrie a cation d'une voiture sur une cha^ de montage : on peut monter de fa¸on ?ne c ind´pendante le moteur et la carrosserie, avant de les assembler. Un autre e exemple provient des choix de cours r´alis´s par des ´tudiants. En effet, ee e certains pr´requis sont parfois n´cessaires. On consid´rera un graphe dont e e e les sommets sont les t^ches (resp. les cours) ` r´aliser (resp. ` suivre) a ae a et si une t^che (resp. un cours) doit ^tre r´alis´e (resp. suivi) avant une a e ee autre (resp. un autre), on tracera un arc orient´ entre les deux sommets e 20 Chapitre I. Premier contact avec les graphes correspondant. La question sous-jacente est de d´terminer une indexation e des sommets d'un graphe orient´ sans cycle de mani`re telle que s'il existe e e un arc de vi a vj , alors i < j . ` Algorithmique Analyse 1 Théorie des graphes Analyse 2 Calculabilité Algorithmique Théorie des graphes Analyse Numérique Analyse 1 Calculabilité Analyse 2 Analyse Numérique Figure I.25. Une application du tri topologique. Exemple I.3.16 (Tournoi). On imagine un ensemble d'´quipes ou de e joueurs et une comp´tition o` chaque joueur affronte tout autre joueur exace u tement une fois. Le seul r´sultat possible est la victoire ou la d´faite. On e e peut alors consid´rer un graphe dont les sommets sont les joueurs et un e arc relie le joueur i au joueur j si i a battu j lors de leur confrontation directe. La question naturelle qui se pose est alors d'essayer de d´terminer e un vainqueur pour la comp´tition. e Exemple I.3.17 (Graphe de De Bruijn). En combinatoire des mots, on ´tudie entre autres, les mots infinis (i.e., les suites infinies w : N -> ? dont e les ´l´ments sont ` valeurs dans un ensemble fini ?). Le graphe de De Bruijn ee a d'ordre k du mot w a pour sommets les facteurs de longueur k de w (i.e., les mots finis de la forme wi · · · wi+k-1 ) et on dispose d'un arc de label ? ? ? entre les sommets ? x et x? si et seulement si ? x? est un facteur de w de longueur k + 1. La figure I.26 repr´sente le graphe de De Bruijn d'ordre 3 e du mot p´riodique abababab · · · . Ces graphes sont en relation directe avec e aba b a bab Figure I.26. Le graphe de De Bruijn d'ordre 3 de ababab · · · . certaines propri´t´s combinatoires des mots correspondants. Par exemple, ee un mot infini est ultimement p´riodique (i.e., il existe des mots finis u et v e tels que w = uvvv · · · ) si et seulement si, pour tout k suffisamment grand, son graphe de De Bruijn d'ordre k contient un unique cycle dont tous les sommets ont un demi-degr´ sortant ´gal ` 1. e e a ee e Exemple I.3.18 (Flot). Une soci´t´ hydro-´lectrique dispose d'un ensemble de canalisations interconnect´es de divers diam`tres et d´sire acheminer e e e I.3. Quelques exemples 21 une quantit´ d'eau maximale d'un point A ` un point B . Quelle quantit´ e a e d'eau peut effectivement ^tre achemin´e et comment l'eau est-elle distribu´e e e e le long du r´seau de canalisations ? On peut imaginer que des contraintes e techniques imposent en outre que chaque canalisation ait un d´bit maximum e et minimum. Un tel exemple est repr´sent´ ` la figure I.27 (les bornes de e ea chaque canalisation sont repr´sent´es par un intervalle, une solution optimale e e est repr´sent´e par un nombre associ´ ` chaque arc). On peut ´galement e e ea e [0,4] [1,4] A 3 2 3 7 [2,7] [2,3] [1,3] [1,2] 3 2 5 [2,8] [0,5] 3 [3,6] 0 10 10 B [8,10] [7,10] Figure I.27. Un probl`me de flot maximum. e prendre en compte une version pond´r´e o` les co^ ts d'entretien des canaee u u lisations pourraient varier. On voudrait alors disposer d'un flot maximum pour un co^ t minimum. u e Exemple I.3.19 (Chemin critique). Un entrepreneur charg´ de construire une maison doit planifier l'accomplissement de plusieurs t^ches : a A: B: C: D: E: F: Creusage des fondations Construction du gros-oeuvre Installation ´lectrique e Installation du chauffage central R´alisation des peintures ext´rieures e e R´alisation des peintures int´rieures e e Ces diverses op´rations sont soumises ` des contraintes temporelles. Cere a taines t^ches ne peuvent d´buter avant que d'autres ne soient achev´es; a e e par contre, certaines peuvent aussi ^tre r´alis´es en parall`le. Par exemple, e ee e les fondations doivent ^tre creus´es avant de d´buter le gros oeuvre. De e e e m^me, l'installation ´lectrique doit ^tre achev´e avant de d´buter les peine e e e e tures int´rieures. Par contre, on peut effectuer simultan´ment les peintures e e ext´rieures et l'installation du chauffage. On consid`re un graphe dont les e e sommets correspondent ` des instants marquant la fin de certaines ´tapes et a e le d´but d'autres. Les arcs sont pond´r´s par le temps n´cessaire ` la r´ae ee e a e lisation d'une t^che. On obtient pour notre exemple, le graphe repr´sent´ a e e a ` la figure I.28 o` 0 repr´sente le d´but des travaux, 1 le d´but du grosu e e e oeuvre, 2 le d´but de l'installation ´lectrique, 3 celui du chauffage, 4 celui de e e la peinture ext´rieure, 5 celui de la peinture int´rieure et enfin, 6 repr´sente e e e la fin des travaux. Sur notre exemple, on voit des pond´rations diff´rentes e e au sortir du sommet 1. Cela peut par exemple signifier que la t^che 2 peut a d´buter sans que le gros-oeuvre ne soit totalement achev´ (par contre, pour e e 22 Chapitre I. Premier contact avec les graphes 2 7 5 40 0 40 1 45 10 5 6 3 3 50 4 Figure I.28. Chemin critique dans la planification de t^ches. a d´buter 4, le gros oeuvre doit ^tre enti`rement termin´, ce qui explique une e e e e pond´ration plus importante). Se d´gage alors la notion de chemin critique, e e chemin de poids maximal entre le d´but et la fin des travaux. En effet, e pour achever la maison, toutes les t^ches auront ´t´ enti`rement ex´cut´es a ee e ee et par cons´quent, il faudra ´galement emprunter le chemin correspondant e e a ` la r´alisation des t^ches les plus lentes. Ce chemin critique permet donc e a de d´terminer le temps minimum n´cessaire ` l'ach`vement des travaux. e e a e 4. Chemins et circuits Les d´finitions suivantes sont somme toute assez naturelles et intuitives, e mais il faut bien les pr´ciser au moins une fois de mani`re rigoureuse pour e e savoir de quoi on parle exactement. e D´finition I.4.1. Soit G = (V, E ) un multi-graphe non orient´9. e Une ar^te peut ^tre e e r´p´t´e plus d'une fois. e ee On a toujours a ~ a. Un chemin de longueur k >= 1 est une suite ordonn´e (e1 , . . . , ek ) de k ar^tes e e adjacentes ei = {ei,1 , ei,2 }, i.e., pour tous i ? {1, . . . , k - 1}, ei,2 = ei+1,1 . Ce chemin de longueur k joint les sommets e1,1 et ek,2 . On dit que le chemin (e1 , . . . , ek ) passe par les ar^tes e1 , . . . , ek (resp. par les sommets e e1,1 , e2,1 , . . . , ek,1 et ek,2 ). On supposera qu'un chemin de longueur 0 (correspondant ` la suite vide) joint toujours un sommet ` lui-m^me. a a e Si les extr´mit´s du chemin sont ´gales, i.e., si e1,1 = ek,2 , on parle plut^t ee e o de cycle, de circuit ou encore de chemin ferm´. Si on d´sire pr´ciser que le e e e chemin consid´r´ n'est pas un cycle, on parlera de chemin ouvert. ee Il se peut que les ar^tes d'un chemin soient toutes distinctes (cela n'implie que pas que les sommets du chemin soient tous distincts). On parle alors de piste ou de chemin ´l´mentaire (voir par exemple, la figure I.29). ee Si les ar^tes d'un chemin sont toutes distinctes et si de plus, les sommets e sont tous distincts10, on parle alors de chemin simple. Bien s^ r, les circuits ´tant des chemins particuliers, on parle aussi de u e circuit ´l´mentaire ou simple (voir par exemple, la figure I.30). Evidemment, ee dans la d´finition d'un circuit simple, on admet que les sommets e1,1 de e d´part et ek,2 d'arriv´e puissent ^tre ´gaux, mais seulement eux. Il est clair e e e e 9Ce graphe peut avoir ou non des boucles, peu importe. 10Sauf dans le cas pathologique du circuit ({a, b}, {b, a}), demander que les sommets d'un chemin soient tous distincts (mis ` part les extr´mit´s du chemin dans le cas d'un a e e circuit), implique que les ar^tes sont aussi toutes distinctes. e I.4. Chemins et circuits 23 e4 e1 e5 e1 e3 e2 e2 e e3 e7 6 Figure I.29. Une piste (ou chemin ´l´mentaire) et un ee chemin simple e e5 6 e4 e7 e3 e2 e4 e1 e1 e e3 6 e2 e5 e 6 e2 e1 e5 e4 e3 Figure I.30. Un circuit, un circuit ´l´mentaire (ou piste ee ferm´e) et un circuit simple. e que tout circuit peut se d´composer en circuits simples. e Remarque I.4.2. Suivant les auteurs, la terminologie peut changer ´nore m´ment. Ainsi, il n'est pas rare (par exemple, pour C. Berge), d'inverser les e d´finitions des adjectifs simple et ´l´mentaire. Pour d'autres, la notion de e ee cycle contient de plus le caract`re ´l´mentaire, voire simple. e ee Remarque I.4.3. Dans le cas d'un graphe (qui n'est pas un multi-graphe), c'est-`-dire pour un 1-graphe, un chemin est aussi univoquement d´termin´ a e e par une suite de sommets (v1 , . . . , vk ) de mani`re telle que {vi , vi+1 } est une e ar^te du graphe. e e D´finition I.4.4. Deux sommets a et b sont connect´s s'il existe un chemin e les joignant, ce que l'on notera a ~ b. La relation ~ "^tre connect´" est e e une relation d'´quivalence sur V . Une classe d'´quivalence pour ~ est une e e composante connexe de G. Un multi-graphe non orient´ est connexe si V /~ e contient une seule classe d'´quivalence, i.e., G poss`de une seule composante e e connexe. Autrement dit, un multi-graphe non orient´ est connexe si, pour e toute paire de sommets, il existe un chemin les joignant. On supposera de plus que G = ({v }, ?) est connexe (ce qui revient ` supposer qu'un chemin a de longueur 0 joint toujours un sommet ` lui-m^me). a e 24 Chapitre I. Premier contact avec les graphes D´finition I.4.5. Soit G = (V, E ) un multi-graphe non orient´ connexe11. e e La distance12 entre deux sommets a et b est la longueur du plus court chemin joignant a et b. On la note d(a, b). Le diam`tre de G est d´fini par e e diam(G) = max d(a, b). a,b?V Si G est en outre pond´r´ par la fonction de poids f : E -> R+ , la ee distance entre les sommets a et b est ´gale au poids minimal des chemins e joignant a et b, i.e., t d(a, b) = min chemin (e1 ,...,et ) joignant a et b i=1 f (ei ). Les d´finitions donn´es pr´c´demment s'adaptent ais´ment au cas d'un e e ee e multi-graphe orient´. Il suffit de respecter en plus le sens de parcours impos´ e e par les arcs. Donnons quelques pr´cisions. e D´finition I.4.6. Soit G = (V, E ) un multi-graphe orient´13. Un chemin e e de longueur k >= 1 est une suite ordonn´e (v1 , . . . , vk ) de k arcs vi = (vi,1 , vi,2 ) e tels que pour tous i ? {1, . . . , k - 1}, vi,2 = vi+1,1 . Ce chemin de longueur k joint les sommets v1,1 et vk,2 . S'il existe un chemin joignant deux sommets a et b, on notera a -> b. Si a -> b et b -> a, on dira que a et b sont fortement connect´s et on notera e a <-> b. Si on impose ` <-> d'^tre r´flexive (i.e., on suppose que a <-> a), on a e e v´rifie ais´ment que la relation <-> "^tre fortement connect´" est une relation e e e e d'´quivalence sur V . Une classe d'´quivalence pour <-> est une composante e e fortement connexe (ou, plus court, f. connexe) de G. Si V /<-> contient une seule classe, on dira que G est fortement connexe (ou f. connexe). Les sommets appartenant ` un cycle maximal, i.e., un cycle auquel on a ne peut adjoindre de nouveaux sommets, constituent une composante f. connexe. Autrement dit, un multi-graphe orient´ G est f. connexe si et e seulement si il existe un cycle passant par chaque sommet de celui-ci. Si on supprime l'orientation des arcs de G et si le multi-graphe non orient´ obtenu de cette mani`re est connexe, alors on dira que G est simplee e ment connexe (ou s. connexe). On pourra bien entendu d´finir, de mani`re e e ´vidente, les composantes simplement connexes (ou s. connexe de G). e e e Remarque I.4.7. Les notions de distance et de diam`tre donn´es dans le cas non orient´ s'adaptent facilement au cas d'un multi-graphe orient´ e e fortement connexe. On remarquera cependant qu'ici, la fonction d(·, ·) n'est en g´n´ral pas sym´trique14. ee e 11Si G n'´tait pas connexe, la fonction distance ne serait pas une fonction totale e d´finie sur V × V tout entier. e 12 V´rifier qu'il s'agit effectivement d'une distance. e 13Ce graphe peut avoir ou non des boucles, peu importe. 14Il ne peut donc pas s'agir ` proprement parler d'une distance. a I.4. Chemins et circuits 25 Exemple I.4.8. Consid´rons le multi-graphe orient´ de la figure I.31 dont e e l'ensemble des sommets est {a, . . . , e} et l'ensemble des arcs est {1, . . . , 7}. Ce graphe est simplement connexe mais il n'est pas fortement connexe. En b 6 1 a 5 3 4 2 d e 7 c Figure I.31. Un graphe orient´. e effet, il n'existe pas de chemin joignant les sommets d ` a. L'ensemble a {b, c, d} est une composante fortement connexe du graphe (les deux autres composantes sont {a} et {e}). Un chemin est par exemple donn´ par (1, 3, 7), e un cycle par (3, 4, 5) et une piste par (1, 3, 4, 5, 6). La distance entre d et c vaut 1. Par contre, la distance entre c et d vaut 2. 4.1. Recherche du plus court chemin. Soit G = (V, E ) un digraphe pond´r´ par la fonction p : E -> R+ . Nous allons pr´senter l'algorithme ee e de Dijkstra de recherche d'un plus court chemin (i.e., un chemin de poids minimal) d'un sommet u fix´ ` un sommet quelconque de G. Il est clair ea que l'on peut restreindre ce probl`me au cas d'un digraphe simple15. Pour e rappel, si u et v sont deux sommets tels que u -> v , le poids d'un chemin (e1 , . . . , ek ) les joignant est i p(ei ). La distance de u ` v est alors le poids a minimal de tels chemins. Si u -> v , on n'a pas ` proprement parler de a distance16 et par convention, on posera que la "distance" de u ` v est alors a + ?. L'algorithme de Dijkstra s'applique ´galement ` un graphe non orient´. e a e Il suffit de remplacer l'ar^te {u, v } de poids ? par deux arcs (u, v ) et (v, u) e ayant chacun un poids ? et ainsi obtenir un digraphe. ` a Remarque I.4.9. Quitte a supposer p ` valeurs dans R+ ? {+?}, on ´tend p de E ` V × V tout entier en posant p(x, x) = 0, pour tout x ? V et e a p(x, y ) = +?, si (x, y ) ? E . C'est ce que nous supposerons par la suite. Intuitivement, l'algorithme fonctionne de la mani`re suivante. A chaque e sommet v de G, on associe une valeur T(v ), initialis´e ` p(u, v ) et une ea liste de sommets C(v ) cens´e correspondre ` un chemin de u ` v . Lorsque e a a 15En effet, passer par une boucle de poids ? > 0 ne ferait qu'augmenter inutilement le poids de ce chemin. De m^me, si plusieurs arcs joignent deux sommets, il suffit de e conserver l'arc de poids minimal. 16Comme nous l'avons d´finie, la distance n'a de sens que sur des digraphes fortement e connexes. 26 Chapitre I. Premier contact avec les graphes l'algorithme s'ach`ve, T(v ) contient le poids minimal des chemins joignant e u ` v et C(v ) r´alise un tel chemin (ou alors, T(v ) = +? si u -> v ). L'id´e a e e est de construire de proche en proche un ensemble X ? V de mani`re telle e qu'un chemin de poids minimal de u ` v ? X passe uniquement par des a sommets de X . L'ensemble X est initialis´ ` {u} et ` chaque ´tape, on ea a e ajoute un sommet ` l'ensemble. a Algorithme I.4.10 (Algorithme de Dijkstra). Les donn´es sont un die graphe simple G = (V, E ) pond´r´ par une fonction p : V × V -> R+ ? {+?} ee (cf. remarque I.4.9) et un sommet u. Pour tout sommet v ? V , T(v ):=p(u, v ), C(v ):=(u, v ) X:={u} Tant que X= V , r´p´ter ee Choisir v ? V \X tel que, pour tout y ? V \X, T(v ) <=T(y )17 X:=X?{v } Pour tout y ? V \X Si T(y )>T(v )+p(v, y ), alors T(y ):=T(v )+p(v, y ) et C(y ):=[C(v ),y ] Dans cet algorithme, la notation [C(v ),y ] repr´sente la liste C(v ) ` laquelle e a on ajoute un ´l´ment y . Intuitivement, lorsqu'on ajoute un sommet v ` X, ee a on regarde s'il est avantageux pour les sommets y ne se trouvant pas dans X de passer par ce sommet v nouvellement ajout´ ` X. Si tel est le cas, on met ea a ` jour les informations concernant y. Avant de d´montrer l'exactitude de cet algorithme, donnons un exemple e d'application de ce dernier. Exemple I.4.11. Voici une application de l'algorithme de Dijkstra au graphe repr´sent´ ` la figure I.32. Pour l'initialisation, prenons X = {a} e ea a 1 c 1 4 b 2 3 2 d 5 f 1 8 e Figure I.32. Un digraphe simple pond´r´. ee et on a a b c d e f v T(v ) 0 1 1 4 +? +? . C(v ) (a, a) (a, b) (a, c) (a, d) (a, e) (a, f ) 17On suppose que r < +?, si r ? R et que +? <= +?. I.4. Chemins et circuits 27 Si le sommet b est choisi (on a le choix entre b et c), on a X = {a, b} et le tableau est mis ` jour : a v a b c d e f T(v ) 0 1 1 3 +? +? . C(v ) (a, a) (a, b) (a, c) (a, b, d) (a, e) (a, f ) A l'´tape suivante, on est forc´ de choisir c. Ainsi, X = {a, b, c} et le tableau e e devient : v a b c d e f T(v ) 0 1 1 3 9 +? . C(v ) (a, a) (a, b) (a, c) (a, b, d) (a, c, e) (a, f ) A pr´sent, d est s´lectionn´, X = {a, b, c, d} et la valeur de C(e) peut ^tre e e e e am´lior´e, ee v a b c d e f T(v ) 0 1 1 3 8 +? . C(v ) (a, a) (a, b) (a, c) (a, b, d) (a, b, d, e) (a, f ) Ensuite, e et f sont choisis successivement mais le tableau ne change plus. Par exemple, on en conclut que le plus court chemin joignant a ` e passe a par b et d et son poids vaut 8. D´monstration. Il est clair que l'algorithme s'ach`ve toujours puisqu'` e e a chaque it´ration de la boucle, un nouvel ´tat est ajout´ a X . Il nous suffit e e e` donc de v´rifier qu'il s'ach`ve avec le r´sultat attendu. Pour ce faire, on e e e proc`de par r´currence sur #X et on v´rifie les deux assertions suivantes e e e pour toutes les valeurs de #X , d'o` le r´sultat annonc´ quand X = V . u e e i) Pour tout v ? X , T(v ) est le poids minimal de tous les chemins joignant u ` v . a ii) Pour tout v ? X , T(v ) est le poids minimal des chemins joignant u ` v qui, ` l'exception de v , passent uniquement par des sommets a a de X . Pour #X = 1, c'est imm´diat car X = {u} et l'initialisation effectu´e dans e e l'algorithme correspond aux assertions. Supposons le r´sultat v´rifi´ pour e ee #X = n et v´rifions-le pour #X = n + 1, 1 <= n < #V . e Lorsque X contient n sommets, l'algorithme stipule de lui ajouter un sommet v ayant une valeur T(v ) minimale parmi les sommets n'appartenant pas ` X . Par l'hypoth`se de r´currence ii), puisqu'` ce stade #X = n et a e e a v ? X , T(v ) est le poids minimal des chemins joignant u ` v qui, ` l'exception a a de v , passent uniquement par des sommets de X . Nous ajoutons ` pr´sent ae v ` X pour obtenir un ensemble de taille n + 1. Proc´dons par l'absurde a e et supposons que T(v ) n'est pas le poids minimal des chemins joignant u ` a v (c'est-`-dire que l'assertion i) n'est pas v´rifi´e). Par cons´quent, il existe a ee e un sommet y ? X et un chemin de u ` v passant par y dont le poids est a strictement inf´rieur ` T(v ). De l`, on en conclut que T(y ) = 1 de cette construction, on choisit un sommet ai+1 de e mani`re telle qu'une ar^te {ai , ai+1 } ? E est s´lectionn´e parmi les #E - i+1 e e e e ar^tes non d´j` s´lectionn´es. Puisque chaque sommet est de degr´ pair, e ea e e e cette s´lection est toujours possible ("lorsqu'on aboutit dans un sommet, e on peut toujours en repartir"). Puisque le graphe est fini, cette proc´dure e s'ach`ve toujours. e On dispose alors d'une piste P joignant a1 ` un certain sommet al . En a fait, on peut supposer que cette piste est ferm´e, i.e., al = a1 . En effet, si al e diff`re de a1 , puisque le degr´ de chaque sommet est pair, on peut ´tendre e e e la piste en ajoutant une ar^te {al , al+1 }. En continuant de la sorte19, on e ´puise les sommets jusqu'` revenir en a1 . e a Si la piste ferm´e P est un circuit eul´rien, le th´or`me est d´montr´. e e ee e e Sinon, il existe un sommet b de P qui est l'extr´mit´ d'un nombre pair ee d'ar^tes n'apparaissant pas dans P . (Une illustration est donn´e ` la fie ea gure I.35. Depuis b, il est possible de construire une piste ferm´e Q form´e e e Q a1 P b Figure I.35. Construction d'un circuit eul´rien. e uniquement d'ar^tes n'apparaissant pas dans P . (On utilise la m^me proc´e e e dure que pr´c´demment; il est clair que le degr´ de chaque sommet est encore ee e pair.) De cette fa¸on, nous avons ´tendu la piste P en une piste plus longue c e P ? Q (couvrant un plus grand nombre d'ar^tes). On obtient alors un circuit e eul´rien en r´p´tant cette ´tape un nombre fini de fois. e ee e e o e Corollaire I.4.17. Le probl`me des sept ponts de K¨nigsberg donn´ dans l'exemple I.3.1 n'admet pas de solution. 19Proc´dons par l'absurde et imaginons un instant ne jamais revenir en a . A chaque e 1 s´lection d'une nouvelle ar^te depuis al , le sommet atteint diff`re donc de a1 et une des e e e ar^tes restantes est consomm´e. Ainsi, le nombre d'ar^tes disponibles d´cro^ strictement. e e e e ?t Pourtant, chaque sommet ´tant de degr´ pair, on peut continuer de la sorte jusqu'` ce e e a qu'il ne reste, dans le pire cas, qu'une seule ar^te disponible, celle retournant ` a1 . e a I.4. Chemins et circuits 31 D´monstration. C'est imm´diat, le graphe de la figure I.12 poss`de un e e e sommet de degr´ 5 et 3 sommets de degr´ 3. e e Corollaire I.4.18. Un multi-graphe non orient´ connexe poss`de un chemin e e eul´rien joignant deux sommets a et b si et seulement si a et b sont les deux e seuls sommets de degr´ impair. e D´monstration. Pour se ramener au th´or`me pr´c´dent, il suffit de cone ee ee sid´rer le graphe G auquel on ajoute une ar^te suppl´mentaire joignant les e e e sommets a et b. e ee e Exemple I.4.19. Fort des r´sultats pr´c´dents, on peut par exemple r´pondre ` la question : "le dessin suivant peut-il ou non ^tre trac´ d'un seul trait, a e e sans lever le crayon et sans repasser deux fois par un trait d´j` trac´ ?". ea e C'est une simple application du corollaire pr´c´dent20. ee 1 0 11 1 00 0 11 00 Figure I.36. Une maison ` tracer d'un seul trait. a Nous pr´sentons succintement l'algorithme de Fleury permettant de conse truire un circuit eul´rien (` supposer qu'un tel circuit existe). Cet algorithme e a repose sur la notion d'ar^te de coupure pr´sent´e ` la section 6. Nous cone e ea seillons donc au lecteur de passer cet algorithme en premi`re lecture. e e a Algorithme I.4.20 (Fleury). La donn´e fournie ` cet algorithme est un graphe simple eul´rien. e Choisir un sommet v0 ? V i:=1 R´p´ter tant que possible ee Choisir une ar^te ei = {vi-1 , vi } ? V telle e ? ei diff`re des ar^tes d´j` choisies e e ea ? autant que ...