Algorithmes de graphes
Les algorithmes de graphes opèrent sur des réseaux de sommets et d'arêtes pour répondre à des questions concernant la connectivité, les distances, les structures couvrantes et les flux — constituant le cœur algorithmique des problèmes modélisés sous forme de graphes.
Definition
Les algorithmes de graphes sont des procédures qui calculent des propriétés ou résolvent des problèmes d'optimisation sur des graphes — des structures mathématiques composées de sommets connectés par des arêtes — tels que l'atteignabilité, les plus courtes distances, les arbres couvrants et les flux maximaux.
Scope
Ce domaine couvre les algorithmes sur les graphes et les réseaux : le parcours systématique (recherche en largeur d'abord et en profondeur d'abord), le calcul des plus courts chemins, les arbres couvrants minimaux, les flux de réseau et l'appariement, ainsi que les problèmes structurels (connectivité, ordre topologique, cycles) qu'ils permettent de résoudre. Il aborde les représentations de graphes (listes et matrices d'adjacence) et leur impact sur le coût algorithmique, et se connecte aux paradigmes de conception (glouton, programmation dynamique) et aux structures de données (files de priorité) sur lesquels les algorithmes de graphes s'appuient. Il exclut l'étude combinatoire abstraite des graphes relevant des mathématiques discrètes.
Sub-topics
Core questions
- Comment un graphe est-il représenté, et comment cette représentation affecte-t-elle l'efficacité de l'algorithme ?
- Comment les parcours en largeur d'abord et en profondeur d'abord révèlent-ils la connectivité et la structure ?
- Comment les plus courts chemins sont-ils calculés sous différentes conditions de poids d'arêtes ?
- Quelles structures couvrent un graphe à coût minimal, et comment sont-elles trouvées ?
- Quelle quantité peut circuler à travers un réseau, et qu'est-ce qui la limite ?
Key concepts
- sommets et arêtes
- liste et matrice d'adjacence
- recherche en largeur d'abord et en profondeur d'abord
- plus courts chemins
- arbre couvrant minimal
- tri topologique
- flux de réseau
- flux maximal coupe minimale
Key theories
- La recherche de graphes comme fondement
- La recherche en largeur d'abord et en profondeur d'abord visitent systématiquement tous les sommets atteignables et constituent la base pour la connectivité, le tri topologique, la détection de cycles et de nombreux autres calculs sur les graphes.
- Dualité flux maximal coupe minimale
- Le flux maximal à travers un réseau est égal à la capacité de sa coupe minimale ; cette dualité, établie par Ford et Fulkerson, sous-tend les algorithmes de flux et se connecte aux problèmes d'appariement et de connectivité.
Clinical relevance
Les algorithmes de graphes modélisent et résolvent une vaste gamme de problèmes réels : le routage et la navigation (plus courts chemins), la conception de réseaux et d'infrastructures (arbres couvrants), la planification et la résolution de dépendances (tri topologique), l'appariement biparti dans l'affectation et la recommandation, et les problèmes de flux en logistique, télécommunications et segmentation d'images.
History
La théorie algorithmique des graphes a connu une croissance rapide au milieu du 20e siècle : l'algorithme de Dijkstra pour les plus courts chemins (1959), les travaux de Ford et Fulkerson sur le flux maximal (1956), et les algorithmes d'arbres couvrants de Kruskal et Prim (1956-1957). Les algorithmes basés sur la recherche en profondeur d'abord de Robert Tarjan dans les années 1970 ont fourni des solutions en temps linéaire à de nombreux problèmes de connectivité, consolidant ainsi les algorithmes de graphes comme un domaine central.
Key figures
- Edsger W. Dijkstra
- Lester Ford
- Delbert Fulkerson
- Robert Tarjan
Related topics
Seminal works
- dijkstra1959
- cormen2009
- kleinberg2006
Frequently asked questions
- Quand devrait-on représenter un graphe comme une liste d'adjacence plutôt qu'une matrice d'adjacence ?
- Les listes d'adjacence utilisent un espace proportionnel au nombre d'arêtes et sont efficaces pour les graphes creux et le parcours. Les matrices d'adjacence utilisent un espace proportionnel au carré du nombre de sommets et permettent des recherches d'arêtes en O(1), ce qui les rend adaptées aux graphes denses ou aux algorithmes qui testent fréquemment les arêtes.
- Les problèmes de graphes sont-ils toujours résolubles efficacement ?
- De nombreux problèmes fondamentaux de graphes (parcours, plus courts chemins, arbres couvrants, flux) disposent d'algorithmes efficaces en temps polynomial, mais d'autres — tels que le problème du voyageur de commerce, la coloration de graphes et la clique maximale — sont NP-difficiles, et sont traités par des méthodes d'approximation ou basées sur la recherche.