Bib 54 - Les graphes
Collectif Tangente
Présentation
SOMMAIRELes onze états du taureau de Picasso / Tous les chemins mènent à Königsberg
Dossier 1 : Les types de graphes
Quelques points et des traits pour les relier suffisent à créer un graphe. Une idée aussi simple se devait d’engendrer un monde foisonnant d'objets: les idées les plus élémentaires sont souvent les plus riches!
Les graphes planaires / Quand les chemins ne se croisent pas / Gardons le sens de l'orientation et restons pondérés! / Obstruction et stabilité / Les matrices entrent en scène / Le graphe de l'amitié et le moulin à vent / Des arbres au secours des probabilités / Des graphes et des surfaces à partir d'un carré / Le théorème des quatre couleurs / Colorier, un défi innocent et redoutable / Le théorème des graphes parfaits / Cliques et théorème de Turan/ La formule d'Euler et les solides de Platon / Le polyèdre de Czà szà r, un monstre topologique / Diagrammes de Schelegel : les polyèdres sont des graphes!
Dossier 2 : Des applications à la vie quotidienne
De par leur structure purement topologique, les graphes sont un puissant outil d'aide à la décision. Ils sont utiles pour planifier et ordonnancer les tâches dans une chaîne de production, gérer les priorités dans un projet, ou hiérarchiser les étapes dans une suite d’instructions informatiques...
La fourmi et le problème du voyageur de commerce / Un projet dans le bon ordre, la méthode PERT /L'algorithme de Dijkstra / Quand le chemin se joue aux dés / Un problème de téléphonie mobile / Desa rbres pour faire passer les trains / Comment éviter les bouchons / Un arbre pour le théâtre / Entre sens et texte / Les livres dont vous êtes le héros
Dossier 3 : Dans L'informatique
Que serait la théorie des graphes aujourd'hui sans l'informatique ? Qu'il s'agisse de trier des données, de compresser des fichiers ou de rechercher un mot dans un texte, on retrouve partout une structure de graphe dans un ordinateur.
Parler à son ordinateur / Retrouver un mot dans un texte / Les réseaux de neurones / Des listes autrement qu'en ligne / Des arbres à compresser
Dossier 4 : Jeux de graphes
La théorie des graphes permet de comprendre, voire de résoudre une grande quantité de jeux de réflexion ou de jeux mathématiques et logiques, parfois de manière inattendue (voir à ce sujet le numéro 46 de la Bibliothèque Tangente). A contrario, les graphes peuvent être à la source d'une catégorie de récréations dont les plus classiques sont des problèmes de labyrinthes.
Arbres, jeux et stratégies / Graphes sur un échiquier / Algorithmes en graphes / Graphes et labyrinthes / Résoudre des énigmes à l'aide des graphes / Jeux et problèmes / Solutions et en bref
Note de lecture Tangente
Des graphes pour représenter le monde
Des points (les sommets) et des traits (les arêtes) pour les relier suffisent à créer un graphe. Une idée aussi simple permet d’engendrer un monde foisonnant d’objets et de relations les reliant. Leurs applications à la vie quotidienne sont nombreuses.
De par leur structure purement topologique, les graphes sont un puissant outil d’aide à la décision. Ils sont utiles pour planifier et ordonnancer les tâches dans une chaîne de production, gérer les priorités dans un projet, ou hiérarchiser les étapes dans une suite d’instructions informatiques...
Qui n’a pas entendu parler du problème du voyageur de commerce, de la méthode PERT ou de l’algorithme de Dijkstra ? La théorie des graphes permet de comprendre, voire de résoudre, une grande quantité de jeux de réflexion ou de jeux mathématiques, parfois de manière inattendue. Elle peut aussi être à la source d’une catégorie de récréations, dont les plus classiques sont des problèmes de labyrinthes.
Après une première partie très théorique, qui présente des résultats peu connus, cet ouvrage s’intéresse aux domaines parfois inattendus dans lesquels interviennent les graphes : transports, téléphonie mobile, littérature, planification de tâches, réseaux, tri de données, labyrinthes, jeu d’échecs...