Hors-série 54 - Les graphes - Des noeuds et des arêtes
Collectif POLE
Présentation
SOMMAIREDossier 1 : Les types de graphes
Quelques points et des traits pour les relief suffisent à créer un graphe. Une idée aussi simple se devait d'engendrer un monde foisonnant d'objets tous plus étonnants les uns que les autres : les graphes planaires sont utilisés pour réaliser des circuits, les graphes binaires sont indispensables à l'informatique, les graphes de Feynman sont omniprésents en physique... Les idées les plus élémentaires sont souvent les plus riches!
Obstruction et stabilité pour classifier les graphes / Des graphes et des surfaces à partir d'un carré / Les graphes planaires éviter les croisements / Des graphes et des diagrammes pour la physique / Diagrammes de Schlegel : les polyèdres sont des graphes
Quand le chemin se joue aux dés / Graphes pondérés et graphes orientés
Dossier 2 : Graphes et décision
De par leur structure purement topologique, les graphes sont un puissant outil d'aide à la décision. Les arêtes munies d'une pondération peuvent aussi bien représenter des distances entre deux sommets connectés que des temps de parcours ou des limites de capacité dans un réseau. C'est le point de départ de l'utilisation des graphes pour planifier et ordonnancer les tâches dans une chaîne de production, hiérarchiser les étapes dans une suite d'instructions informatiques... et même constituer un réseau de voies pour faire passer des trains!
La fourmi et le problème du voyageur de commerce / Un projet dans le bon ordre: la méthode PERT / L'algorithme de Dijkstra / Arbres, jeux et stratégies / La recherche opérationnelle / Des arbres pour faire passer des trains
Et aussi
Tous les chemins mènent à Königsberg / Développements actuels
Et toujours
En bref - notes de lecture - problèmes et solutions
.jpg)
