Vuibert Théorie des graphes

Description

La théorie des graphes est issue de problèmes ayant l'allure de jeux mathématiques, comme le problème du « voyageur de commerce » : tracer le plus court chemin que pourrait emprunter un représentant pour rendre visite à ses clients dans une série de villes, en ne passant qu'une seule fois dans chaque ville. Elle a d'abord trouvé des applications en théorie des probabilités.Ses applications actuelles sont orientées vers la logistique et l'informatique (optimisation des réseaux de transport, de personnes, de marchandises ou de données, optimisation des itinéraires, du stockage, Internet, GPS, architecture des ordinateurs) et elle suscite de ce fait un intérêt grandissant. En retour, on utilise abondamment l'informatique pour donner des solutions pratiques aux problèmes de graphes que l'on se pose, d'où l'importance donnée dans ce livre aux algorithmes.La théorie des graphes a été introduite il y a une quinzaine d'années dans les programmes du secondaire français, et ce livre a été écrit à cette occasion, à l'intention des professeurs.Un graphe se définit simplement comme un ensemble de points dont certains sont reliés par des lignes.Le premier problème considéré comme un problème de théorie des graphes est celui des sept ponts de Königsberg (Euler, 1736), qu'on peut aisément transposer à Paris : peut-on effectuer une promenade qui nous ramène à notre point de départ en empruntant une fois et une seule chacun des ponts de la ville ?La formulation de ce problème comme un problème de graphes fait intervenir quatre points, A, B, C, D représentant respectivement la rive droite, la rive gauche, l'île de la Cité et l'île Saint-Louis, et des lignes reliant ces points, représentant les ponts. Le célèbre problème des quatre couleurs (peut-on colorier n'importe quelle carte avec quatre couleurs seulement, de façon que deux pays voisins n'aient pas la même couleur ?) peut aussi se traduire un termes de graphes : un point par pays, une ligne reliant deux points si les deux pays…

Source : fiche du marchand Cultura FR.