Remerciez-le!

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

Alain Bretto Alain Faisant François Hennecart Éléments de théorie des graphes 2

Alain Bretto Alain Faisant François Hennecart Éléments de théorie des graphes 2e édition revue et augmentée C O L L E CT I O N I R I S Sous la direction de Nicolas Puech x6 x1 x2 x9 x3 x4 x5 x7 x8 Collection IRIS Dirigée par Nicolas Puech Alain Bretto Alain Faisant François Hennecart editions.lavoisier.fr Éléments de théorie des graphes 2e édition revue et augmentée © 2018, Lavoisier, Paris ISBN : 978-2-7462-4850-2 Direction scientifique : Nicolas Puech Direction éditoriale : Jean-Marc Bocabeille À la mémoire de ma mère, Alain Bretto Préface de la deuxième édition Avant donc que d’écrire, apprenez à penser. Selon que notre idée est plus ou moins obscure, L’expression la suit, ou moins nette, ou plus pure. Ce que l’on conçoit bien s’énonce clairement, Et les mots pour le dire arrivent aisément. (...) Hâtez-vous lentement, et, sans perdre courage, Vingt fois sur le métier remettez votre ouvrage Polissez-le sans cesse et le repolissez ; Ajoutez quelquefois, et souvent eﬀacez. (...) Il faut que chaque chose y soit mise en son lieu ; Que le début, la ﬁn, répondent au milieu ; Que d’un art délicat les pièces assorties N’y forment qu’un seul tout de diverses parties, Que jamais du sujet le discours s’écartant N’aille chercher trop loin quelque mot éclatant. Boileau, L’art poétique, chant I (1674) Dans cette deuxième édition nous avons entièrement revu le chapitre concernant les algorithmes, en mettant l’accent sur la récursivité. Quelques aménagements, précisions et compléments ont été faits pour les graphes planaires. La théorie spectrale a été considérablement développée, avec no- tamment l’étude des graphes de Cayley. Nous avons ajouté un chapitre sur les graphes aléatoires, et complété par quelques perspectives concer- nant l’analyse sur graphes. Les graphes sont des objets très simples et susceptibles de nombreuses variations. Il n’est pas toujours facile d’arbitrer entre la rigueur et l’intui- tion : ainsi la notion de cycle pourrait être décrite de façon plus précise en introduisant par exemple le sens de parcours, mais cela conduit à alourdir tellement les déﬁnitions qu’elles en deviennent inutilisables ! Nous avons donc fait de notre mieux, bien conscients (comme Boileau ...) que l’ou- vrage n’est pas parfait ! Saint-Étienne, avril 2018, A. Bretto, A. Faisant, F. Hennecart À propos des auteurs Alain Bretto est professeur d’informatique à l’Université de Caen Normandie. Il enseigne également à AgroParisTech et a précédemment enseigné aux États-Unis et en Italie. Ses recherches portent sur la théo- rie des graphes et des hypergraphes, plus précisément sur leurs aspects algébriques et topologiques. Expert reconnu dans ces domaines, il s’inté- resse aussi aux applications des mathématiques : analyse d’images, ﬁnance, technologie de l’information. Alain Faisant a été maître de conférences en mathématiques à l’Uni- versité de Saint-Étienne, où s’est déroulée la majeure partie de sa carrière. Il continue à y développer ses recherches. Ses travaux sont principalement centrés sur la théorie des nombres et il est l’auteur d’un ouvrage qui fait ré- férence sur le sujet : L’équation diophantienne du second degré (Hermann, 1991). François Hennecart est professeur de mathématiques à l’Université de Saint-Étienne, où il développe ses recherches en théorie des nombres. Il s’intéresse plus particulièrement à des problèmes additifs et combinatoires, domaines où les graphes interviennent fréquemment. Avant-propos à la première édition En quelques décennies, la théorie des graphes est devenue l’un des domaines les plus féconds et les plus dynamiques des mathématiques et de l’informatique. Cette évolution constante est sans doute due au large spectre des applications telles que l’électronique, la linguistique, la chimie, la sociologie, les mathématiques, l’informatique. . . Le début a été hésitant : l’histoire veut que la théorie des graphes ait commencé avec l’article du mathématicien suisse Leonhard Euler sur le problème des ponts de Königsberg (voir Solutio problematis ad geome- triam situs pertinentis, Commentarii Academiae Scientiarum Imperialis Petropolitanae Vol 8 (1736), 128–140). Néanmoins il faudra attendre deux siècles pour que le premier livre pa- raisse sur le sujet. Celui-ci a été écrit par Dénes König en 1936 (voir Theo- rie der Endlichen und Unendlichen Graphen, Teubner, Leipzig, 1936). Le développement de la théorie des graphes est assez similaire au dé- veloppement de la théorie des probabilités dont beaucoup de résultats sont dus à l’eﬀort de compréhension des jeux de hasard. Les graphes ont d’abord été considérés comme curiosité mathématique et comme outil pour étudier les jeux logiques : on peut citer par exemple le problème du ca- valier du jeu d’échec devant visiter chaque case de l’échiquier exactement une fois tout en revenant à la case de départ. Ils sont devenus maintenant incontournables dans diverses activités humaines. À la suite d’Euler, beaucoup de mathématiciens se sont intéressés aux graphes ; citons en quelques-uns : – Edouard Lucas pose le problème des demoiselles : des jeunes ﬁlles, en nombre pair, se promènent chaque jour deux par deux. On de- mande comment il faut disposer les promenades de sorte que cha- cune d’entre elles se retrouve une et une fois seulement en compa- gnie de chacune des autres. x Éléments de théorie des graphes Nous développons au chapitre 8 les outils qui permettent de ré- soudre ce type de problème. – En 1856, William R. Hamilton étudie un problème apparemment aussi simple, celui de trouver un chemin passant une fois et une seule par chaque sommet d’un graphe. Cela donnera naissance au concept de graphe hamiltonien (voir chapitre 2). – Arthur Cayley, James J. Sylvester puis George Pólya déve- loppent la notion d’arbre (voir chapitre 2). – En 1840, August F. Möbius propose le problème suivant : un roi a cinq ﬁls et souhaite qu’à sa mort son royaume soit divisé en cinq provinces de telle sorte que chaque province ait une frontière com- mune avec chacune des autres. Cela revient à décider si le graphe K5 est planaire. Nous aborderons la notion de graphe planaire au chapitre 5. Cette théorie permet de représenter un ensemble complexe d’objets en exprimant les relations entre les éléments ; par exemple réseaux de com- munication, génétique, circuits électriques, mais également en mathéma- tiques : la classiﬁcation des groupes simples ﬁnis fait appel aux graphes par l’intermédiaire des cartes et des dessins d’enfant (redécouverts en 1984 par Alexandre Grothendieck dans Esquisse d’un programme). Il faudra néanmoins attendre le milieu du xxe siècle pour qu’une étude systématique soit entreprise. Aujourd’hui c’est une théorie foisonnante aux frontières de domaines plus classiques tels que la topologie, l’algèbre, la géométrie, l’al- gorithmique et ses applications. Son langage et ses notations ne sont pas encore stabilisés et sont parfois liés au domaine dans lequel la théorie des graphes est employée. Nous avons essayé dans cet ouvrage d’uniﬁer les déﬁnitions et les ré- sultats, et de les placer dans le cadre le plus général possible. Cependant il n’est pas facile d’avoir le même langage pour les graphes simples, les multigraphes, les graphes orientés (ou digraphes). . . Le contenu n’est pas standard (bien que beaucoup de chapitres traitent d’éléments classiques) au sens d’une introduction habituelle aux graphes. Nous avons insisté sur l’aspect algébrique et topologique, mais également sur les derniers dévelop- pements de la théorie (notamment les aspects spectraux, voir chapitre 9). Aﬁn de rendre le lecteur autonome, nous avons volontairement détaillé les preuves et introduit des rappels tout au long de l’ouvrage. Certains cha- pitres et paragraphes de ce livre ne sont pas faciles et peuvent être omis en première lecture. Néanmoins le but aﬃrmé de ce livre est d’emmener le lecteur au seuil de la recherche. Avant-propos xi Dans le premier chapitre, nous introduisons les graphes et le langage de base. Certaines notions élémentaires sur la complexité algorithmique sont également abordées ; les deux derniers paragraphes sont d’un niveau un peu plus élevé et peuvent être ignorés lors d’une première lecture. Le deuxième chapitre a pour objet l’introduction de diﬀérentes classes de graphes (graphes bipartis, arbres, arborescences. . .). Les derniers para- graphes traitent des graphes eulériens et hamiltoniens. Dans le chapitre trois, nous étudions les relations entre les graphes et les structures de données algorithmiques. De manière plus précise, nous mon- trons que la notion de graphe est fondamentale quand on veut représenter des données informatiques. Des notions telles que les arbres binaires de recherche, les arbres de priorité, les tas. . . sont abordés. Ce chapitre est un cours classique d’algorithmique et de structures de données généralement étudié en première et deuxième années de licence d’informatique. Ces trois chapitres n’utilisent aucun concept diﬃcile et peuvent être lus par un étudiant ayant le niveau d’un baccalauréat scientiﬁque : ils néces- sitent cependant quelques compléments sur des structures mathématiques généralement abordées en début d’études supérieures, qui sont introduits au cours du texte. Le chapitre quatre, qui introduit la connexité et les ﬂots, bien que n’utilisant aucune notion diﬃcile, est un peu plus théorique. Néanmoins il peut être lu par une personne ayant un niveau licence première et deuxième années en mathématiques ou informatique. Le chapitre cinq traite de la notion de planarité et ne peut être abordé que par un lecteur ayant de bonnes notions uploads/Litterature/ theorie-des-graphe.pdf