Exposé de P. Pesneau dans le cadre de la journée IREM
Si on représente un réseau de télécommunications sous la forme d'un graphe, une condition de fiabilité consiste à imposer l'existence de deux chemins arête-disjoints entre chaque paire de sommets du graphe. Ainsi, si un lien de communication vient à tomber en panne, il existe toujours un second chemin pour transmettre l'information. En associant un coût de construction à chaque lien qu'il serait possible d'établir dans le réseau, le problème qui se pose est de chercher un sous-graphe de coût minimum vérifiant la condition de fiabilité ci-dessus. Nous pourrons ajouter des conditions supplémentaires afin d'assurer une qualité de service minimum en cas de panne.
Les approches polyédrales permettent la résolution de ce type de problème (nommé programme linéaire en nombres entiers). Nous en ferons une présentation puis l'illustrerons avec l'exemple précédent.
Page des journées IREM
https://math-interactions.u-bordeaux.fr/Centres-de-ressources/IREM/Journees-IREM
Mots clés : irem