[PDF] [PDF] Théorie des Graphes - Centre Inria dUniversité Côte dAzur

View - Download [PDF] Théorie des Graphes - Centre Inria dUniversité Côte dAzur

Previous PDF

Next PDF

J.A. Bondy et U.S.R. MurtyTraduit de l"anglais par F. HavetTh´eorie des Graphes c ?2008 J.A. Bondy and U.S.R. MurtyAll rights reserved D´edicaceA la m´emoire de nos chers amis et mentors

Claude Berge Paul Erdos Bill Tutte

Avant-proposPendant plus d"un si`ecle, l"essor de la th´eorie des graphes a ´et´elargement inspir´e

et guid´e par la Conjecture des Quatre Couleurs. La r´esolution decette conjecture par K. Appel et W. Haken en 1976, l"ann´ee de la publication de notre premier livreGraph Theory with Applications, a marqu´e un tournant dans son histoire. Depuis lors, le sujet a connu une croissance exponentielle, due pourune large part `a son rˆole de structure essentielle dans les math´ematiquesappliqu´ees mod- ernes. L"informatique et l"optimisation combinatoire, en particulier, s"appuient sur la th´eorie des graphes et contribuent `a son d´eveloppement. Deplus, dans un monde o`u les communications sont d"une importance capitale, la grande adaptabilit´e des graphes les rend indispensables `a la conception et `a l"analyse des r´eseaux de com- munication. S"appuyant sur les fondations laiss´ees par Claude Berge, Paul Erdos, Bill Tutte, et d"autres, une nouvelle g´en´eration de th´eoriciens des graphes a enrichi et trans- form´e le sujet en d´eveloppant des nouvelles techniques puissantes, beaucoup ´etant emprunt´ees `a d"autres domaines des math´ematiques. Celles-ciont conduit, en par- ticulier, `a la r´esolution de plusieurs anciennes conjectures, notamment la Conjec- ture Forte des Graphes Parfaits de Berge et la Conjecture de Kneser, toutes deux sur les colorations, et la Conjecture de Gallai sur les couvertures par cycles. Un des d´eveloppements les plus spectaculaires de ces trente derni`eres ann´ees est la cr´eation de la th´eorie des mineurs de graphes par G. N. Robertson et P. D. Seymour. Dans une longue s´erie d"articles profonds, ils ont r´evolutionn´e la th´eorie des graphes en introduisant une mani`ere originale et lumineuse de voir la structure de graphe. Con¸cue pour attaquer une c´el`ebre conjecture de K. Wagner, leur th´eorie donne une importance accrue aux plongements de graphes dans lessurfaces. Elle a ´egalement conduit `a des algorithmes en temps polynomial pour r´esoudre quan- tit´e de probl`emes jusqu"alors insolubles, comme celui de trouverune collection de chemins deux `a deux disjoints entre des paires de sommets donn´ees. Une technique qui a connu un succ`es spectaculaire est la m´ethode probabiliste. Introduite dans les ann´ees 1940 par Erdos, en collaboration avec ses compatri- otes hongrois A. R´enyi et P. Tur´an, cette technique puissanteet d"une grande

X Avant-propossouplesse est employ´ee de plus en plus fr´equemment et de fa¸conde plus en plus

sophistiqu´ee pour ´etablir l"existence ou la non-existence de graphes, ou d"autres structures combinatoires, ayant des propri´et´es particuli`eres. Ainsi que not´e pr´ec´edemment, la croissance de la th´eorie des graphes est large- ment due `a son rˆole fondamental pour les sciences appliqu´ees. En particulier, la recherche d"algorithmes efficaces a aliment´e beaucoup de recherches sur la struc- ture des graphes. L"importance des arbres couvrants de diff´erents types, tels que les arbres en largeur et en profondeur, est d´esormais ´evidente, et les d´ecompositions arborescentes de graphes sont un ´el´ement central dans la th´eorie des mineurs de graphes. La th´eorie algorithmique des graphes emprunte des outils d"un certain nombre de disciplines, notamment la g´eometrie et la th´eorie des probabilit´es. La d´ecouverte par S. Cook, dans les ann´ees 1970, de l"existence dela vaste classe des probl`emes apparemment insolublesNP-complets a conduit `a la recherche d"algorithmes d"approximation efficaces, l"objectif ´etant d"obtenir une bonne ap- proximation de la v´eritable valeur. L`a encore, les m´ethodes probabilistes s"av`erent indispensables. Les liens entre la th´eorie des graphes et les autres branches des math´ematiques deviennent de plus en plus ´etroits, ce qui est une indication de la maturit´e crois- sante du sujet. Nous avons d´ej`a ´evoqu´e certaines relationsavec la topologie, la g´eometrie, et les probabilit´es. Des outils d"alg`ebre, d"analyse, etde th´eorie des nombres sont ´egalement employ´es avec des r´esultats consid´erables.`A l"inverse, des m´ethodes de th´eorie des graphes sont de plus en plus utilis´ees dans d"autres domaines des math´ematiques. Un exemple notable est le Lemme de R´egularit´e de Szemer´edi. Con¸cu pour r´esoudre une conjecture d"Erdoset Tur´an, il est de- venu un outil essentiel en th´eorie additive des nombres, ainsi qu"en combinatoire extr´emale. Une description d´etaill´ee de cette interaction se trouve dans le livre en deux volumesHandbook of Combinatorics. Il devrait ˆetre ´evident au vu des remarques ci-dessus que la th´eorie des graphes est une discipline en plein essor. Elle contient un ensemble de th´eor`emes beaux et puissants qui s"appliquent largement. La croissance remarquable du sujet se reflte dans la richesse des livres et monographies qui sont maintenant disponibles. En plus duHandbook of Combinatorics, dont la plus grande partie est d´edi´ee `a la th´eorie des graphes, et du trait´e d"optimisation combinatoire entrois volumes de Schrijver (2003), destin´e `a devenir un classique, on trouve des livres sur la coloration par Jensen et Toft (1995), les flots par Zhang (1997),les couplages par Lov´asz et Plummer (1986), la th´eorie extr´emale des graphes par Bollob´as (1978), les graphes al´eatoires par Bollob´as (2001) et Janson et al. (2000), les m´ethodes probabilistes par Alon et Spencer (2000) et Molloy et Reed (1998), lath´eorie topologique des graphes par Mohar et Thomassen (2001), la th´eorie alg´ebrique des graphes par Biggs (1993), et les graphes orient´es par Bang-Jensen et Gutin (2001), ainsi qu"un grand choix de manuels. Un autre signe est le nombre important de nouvelles revues d´edi´ees `a la th´eorie des graphes. Le pr´esent projet a commenc´e avec pour seule intention de fairedes r´evisions mineures `a notre pr´ec´edent livre. Cependant, nous avons vitepris conscience que

Avant-propos XI

l"´evolution de la discipline r´eclamait une r´eorganisation totale et une augmentation de son contenu. De mˆeme que pourGraph Theory with Applications, notre but premier est de pr´esenter une introduction coh´erente du sujet, qui puisse servir de manuel pour des ´etudiants de premier cycle ou deuxi`eme cycle enmath´ematique et informatique. Pour des raisons p´edagogiques, nous avons mis l"accent sur des sujets qui peuvent ˆetre abord´es de mani`ere satisfaisante dans un cours. L"omission la plus visible est la th´eorie des mineurs de graphes, que nous ne faisons qu"effleurer ; elle est trop complexe pour recevoir un traitement ad´equat. Nousavons gard´e autant que possible la terminologie et la notation de notre livre pr´ec´edent, qui sont maintenant largement adopt´ees. Nous avons pris un soin particulier `a fournir un traitement syst´ematique de la th´eorie des graphes sans pour autant sacrifier son attrait intuitif et esth´etique. Les techniques de preuve couramment utilis´ees sont d´ecrites etillustr´ees. Nombre d"entre elles se trouvent dans des encarts, alors que d"autres, tels que les parcours, les flots dans les r´eseaux, le Lemme de R´egularit´e et le Lemme Local, sont les sujets de parties ou de chapitres entiers. Les exercices, de diff´erents niveaux de difficult´e, ont ´et´e con¸cus pour aider le lecteur `a maitriser ces techniques et `a renforcer sa compr´ehension du sujet. Les exercices qui sont n´ecessaires `a la bonne compr´ehension du texte sont indiqu´es par une ´etoile. Les exercices les plus difficiles sont s´epar´es des plus faciles par une ligne de d´emarcation. Le second objectif de ce livre est de servir d"introduction `a la recherche en th´eorie des graphes.`A cette fin, nous avons inclus des parties sur des sujets plus avanc´es, et un certain nombre de probl`emes ouverts int´eressants et difficiles sont mis en exergue et d´etaill´es. Ceux-ci ainsi que beaucoup d"autres sont r´eunis dans une liste en appendice. Malgr´e ce contenu plus avanc´e, le livre est organis´e de telle sortequ"un cours d"introduction `a la th´eorie des graphes puisse se baser sur les premi`eres parties de chapitres bien choisis. Comme la th´eorie des nombres, la th´eoriedes graphes est conceptuellement simple, mais contient des probl`emes ouverts tr`es difficiles. Comme la g´eom´etrie, elle se visualise agr´eablement. Ces deux aspects, ainsi que ses nombreuses applications, font de la th´eorie des graphes un sujet id´eal `a inclure dans les programmes math´ematiques. Nous avons cherch´e `a transmettre le charme esth´etique de la th´eorie des graphes en illustrant le texte de nombreux graphes int´eressants - une listecompl`ete se trouve en index. Le dessin de la couverture, tir´e du Chapitre 10, repr´esente des plongements simultan´es deK6et de son dual, le graphe de Petersen, dans le plan projectif.

Une page Web pour le livre est disponible `a

http://blogs.springer.com/bondyandmurty Le lecteur y trouvera des indications sur un choix d"exercices, des mises en per- spectives des probl`emes ouverts, et tout autre contenu suppl´ementaire, ainsi que l"in´evitable liste d"errata. Pour les enseignants qui souhaitent utiliser ce livre comme base pour un cours, des suggestions sont donn´ees pour faire un choix judi- cieux de sujets, en fonction de l"auditoire vis´e.

XII Avant-propos

Nous sommes redevables `a de nombreux amis et coll`egues de leur int´erˆet et leur contribution `a ce projet. Tommy Jensen m´erite des remerciements sp´eciaux. Il a lu int´egralement le manuscrit, a ´emis de nombreux commentaires infailliblement

pertinents, a simplifi´e et clarifi´e plusieurs d´emonstrations, a corrig´e de nombreuses

erreurs techniques et des maladresses linguistiques, et a fait de pr´ecieuses sugges- tions. D"autres ont parcouru le livre et ont comment´e certaines parties du livre dont Noga Alon, Roland Assous, Xavier Buchwalder, Genghua Fan, Fr´ed´eric Havet, Bill Jackson, Stephen Locke, Zsolt Tuza, et deux rapporteurs anonymes. Nous avons eu ainsi la chance de b´en´eficier de leur excellente connaissance etde leur goˆut sˆur. Des coll`egues nous ont donn´e des conseils ou nous ont fourni des exercices, des probl`emes, et d"autres ´el´ements utiles, notamment Michael Albertson, Marcelo de Carvalho, Joseph Cheriyan, Roger Entringer, Herbert Fleischner, Richard Gibbs, Luis Goddyn, Alexander Kelmans, Henry Kierstead, L´aszl´o Lov´asz, Cl´audio Lucch- esi, George Purdy, Dieter Rautenbach, Bruce Reed, Bruce Richmond, Neil Robert- son, Alexander Schrijver, Paul Seymour, Mikl´os Simonovits, Bal´azs Szegedy, Robin Thomas, St´ephan Thomass´e, Carsten Thomassen, et Jacques Verstra¨ete. Nous les remercions tous chaleureusement pour leurs diverses contributions. Nous sommes aussi reconnaissants `a Martin Crossley pour nous permettre d"utiliser (Fi- gure 10.24) les dessins du ruban de M¨obius et du tore tir´es de son livre Crossley (2005). Mat´eriel et soutien nous ont gentiment ´et´e apport´es par Maurice Pouzet `a

l"Universit´e Lyon 1 et Jean Fonlupt `a l"Universit´e Paris 6. Le glossaire a ´et´e pr´epar´e

en utlisant le logiciel con¸cu par Nicola Talbot de l"University of East Anglia. Les

conseils qu"ils nous a diligemment offerts ont ´et´e tr`es appr´eci´es. Enfin, nous avons

b´en´efici´e de relations productives avec Karen Borthwick `a Springer, et de l"aide technique fournie par ses coll`egues Brian Bishop et Frank Ganz. Nous d´edions ce livre `a la m´emoire de nos amis Claude Berge, Paul Erdos, et Bill Tutte. Il doit son existence `a leurs r´ealisations, leurs exemples inspirants et leur gentillesse personnelle.

J. A. Bondy et U. S. R. Murty

Septembre 2007

Pr´eface `a la seconde ´edition

Nous avons saisi l"occasion de cette deuxi`eme ´edition pour corriger un certain nom- bre d"erreurs. La plupart d"entre elles ont d´ej`a ´et´e indiqu´eessur le blog du livre. Nous avons ´egalement apport´e des modifications mineures `a quelques exercices, en reclassifiant certains de facile `a difficile et vice-versa, ou en d´epla¸cant certains dans de nouvelles parties voire de nouveaux chapitres. Huit exercices dela Partie 11.2

Avant-propos XIII

ont ´et´e mis `a leur place ad´equate Partie 11.1, par exemple. En outre, plusieurs nou- veaux exercices ont ´et´e ajout´es.Par cons´equent, de nombreux num´eros d"exercices ont chang´e depuis la premi`ere ´edition. Plus important, nous avons d´eplac´edu contenu (le Th´eor`emede Gallai-Milgram et la Conjecture de Partition en Chemins de Berge) de la Partie 19.2 aux Parties

12.1 et 14.1

1, respectivement, et quelque peu remodel´e les Parties 15.5 et 15.6.

J. A. Bondy et U. S. R. Murty

Juin 2008

Pr´eface du traducteur

Depuis un demi-si`ecle, la th´eorie des graphes a connu des d´eveloppements spec- taculaires. Domaine d´esormais bien ´etabli, elle a de nombreux liens avec d"autres branches des math´ematiques, et de nombreuses applications en d"autres sciences telles que l"informatique, la physique, la biologie et les sciences humaineset so- ciales. Elle est donc largement enseign´ee dans de nombreux cursusuniversitaires. Quelques ´el´ements de th´eorie des graphes sont ´egalement auprogramme de cer- taines s´eries de lyc´ee. Malheureusement, depuis le livreGraphes et Hypergraphes ´ecrit par Claude Berge en 1969, aucun livre en langue fran¸caise n"atrait´e de ce sujet. Il me semblait donc n´ecessaire de r´eparer ce manque, d"autant que tr`es r´eguli`erement des coll`egues, qu"ils soient universitaires ou enseignants en lyc´ee, me demandaient de leur conseiller un ouvrage en fran¸cais sur la th´eorie des graphes, pour leur usage ou celui de leurs ´etudiants. Une possibilit´e aurait ´et´e d"´ecrire un nouveau livre moi-mˆeme, mais cela ne m"aurait conduit qu"`a accoucher d"une pˆale copie duGraph Theoryde Bondy et Murty. En effet, ce livre, r´ef´erence indiscutable du domaine, pr´esente un panorama complet de la th´eorie des graphes d"aujourd"hui. Plus important, celivre s"adresse `a un public tr`es large : il donne au n´eophyte une excellente introduction `a la th´eorie des graphes ; le lecteur plus confirm´e peut s"y perfectionner et y trouver des pointeurs vers des sujets de recherches ; les enseignants peuvent s"en servir pour construire de nombreux cours s"adressant `a des auditoirestr`es vari´es. Enfin, sa r´edaction est commun´ement salu´ee pour son intelligence et saclart´e. Il m"est

1NdT: Cette num´erotation est celle de la pr´esente version fran¸caise. La num´erotation

dans la deuxi`eme ´edition anglaise ´etait 14.1. De mˆeme, les num´erotations 15.5 et 15.6

`a la fin de la phrase sont celles de cette version et correspondent au 14.5 et 14.6 de la deuxi`eme ´edition anglaise.

XIV Avant-proposdonc tr`es rapidement apparu que le plus judicieux ´etait de traduire ce livre. J"esp`ere

que toutes les qualit´es de celui-ci auront ´et´e restitu´ees dansla pr´esente traduction.

Tr`es peu de modifications ont ´et´e apport´ees lors de la traduction (`a partir de la seconde ´edition). En accord avec les auteurs, j"ai cependant d´ecid´e de d´edier un chapitre au Lemme de R´egularit´e afin d"une part de mettre plus l"accent sur cet outil tr`es important et d"autre part de le pr´esenter apr`es la m´ethode probabiliste. Ce nouvel ordre me semble plus naturel car le Lemme de R´egularit´ed´ecoupe le graphe en parties telles que la r´epartition des arˆetes entre deuxparties a des propri´et´es semblables `a une r´epartition al´eatoire. La partie du Chapitre 12 de la

version originale qui concerne le Lemme de R´egularit´e a donc ´et´eˆot´ee de celui-ci

et remani´ee afin d"en faire le nouveau Chapitre 14. Les chapitres qui suivent ont donc une num´erotation d´ecal´ee de 1 par rapport au livre original. Avec Adrian Bondy et Rama Murty, nous avons mis `a jour la liste de probl`emes ouverts. En effet, depuis la parution de la version anglaise, cinq conjectures ont

´et´e montr´ees ou infirm´ees ; elles ont donc ´et´e retir´ees. Afin de maintenir une liste

de 100 probl`emes ouverts, nous en avons donc ajout´e autant. Je suis reconnaissant `a certains coll`egues pour m"avoir soutenudans ma tˆache. Une mention sp´eciale revient `a Eric Sopena qui a relu l"int´egralit´e de ce livre, y traquant scrupuleusement les fautes d"orthographes et les tournures malheureuses. Les avis de Jean-Claude Bermond et de St´ephane P´erennes m"ont´egalement ´et´e pr´ecieux dans le choix de la terminologie. Enfin, je tiens `a remercierJean-Claude Bermond, Olivier Delmas, Nicolas Nisse et Valentin Weber pour avoir reluune partie du manuscrit.

F. Havet

D´ecembre 2014

Table des mati`eres1 Graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 1

2 Sous-graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3 Graphes connexes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4 Arbres. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 105

5 Graphes non-s´eparables. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

6 Algorithmes de parcours. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

7 Flots dans les r´eseaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

8 Complexit´e des Algorithmes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183

9 Connexit´e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 217

10 Graphes planaires. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255

11 Le Probl`eme des Quatre Couleurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

12 Stables et Cliques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

13 La M´ethode Probabiliste. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339

14 Le Lemme de R´egularit´e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369

15 Coloration des sommets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

16 Colorations de Cartes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421

17 Couplages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 443

XVI Table des mati`eres18 Coloration des arˆetes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483

19 Cycles hamiltoniens. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505

20 Couvertures et Paquets dans les Graphes Orient´es. . . . . . . . . . . . . 539

21 Circuits ´electriques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 561

22 Flots Entiers et Couvertures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593

Probl`emes ouverts. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623

Litt´erature. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 633

Notations Math´ematiques G´en´erales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665

Param`etres de Graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667

Op´erations et Relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669

Familles de Graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671

Structures. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 673

Autres Notations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675

Index. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 679

1GraphesSommaire

1.1 Graphes et leur repr´esentation . . . . . . . . . . . . . . . . . . . .1

D efinitions et exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1quotesdbs_dbs50.pdfusesText_50

[PDF] cours théorie générale du droit constitutionnel maroc

[PDF] cours thermodynamique statistique mp

[PDF] cours tourisme gratuit

[PDF] cours transaction immobilière

[PDF] cours transaction immobilière bts pi

[PDF] cours transfert thermique pdf

[PDF] cours transport routier pdf

[PDF] cours trigonométrie pdf

[PDF] cours trigonométrie première s

[PDF] cours tva maroc pdf

[PDF] cours typologie des textes narratifs s1 pdf

[PDF] cours ue4 paces pdf

[PDF] cours vanne

[PDF] cours vba excel 2013 pdf

[PDF] cours vecteurs 1ere s pdf