Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Orientation forte
Résumé
Une orientation forte est, en théorie des graphes, l'attribution d'un sens à chaque arête d'un graphe non orienté (une orientation) qui en fait un graphe fortement connexe. Par exemple, on peut attribuer une orientation forte à un réseau routier s'il est possible de faire de chaque rue un sens unique sans rendre aucune intersection inaccessible.
Le théorème de Robbins caractérise les graphes fortement orientables, qui sont exactement les graphes connexes sans pont. Les orientations eulériennes et les orientations bien équilibrées sont des cas particuliers d'orientations fortes. Pour les graphes non connexes, la notion d'orientation forte se généralise par les orientations totalement cycliques.
L'ensemble des orientations fortes d'un graphe forme un cube partiel, dont les orientations adjacentes diffèrent par l'orientation d'une seule arête. Étant donné un graphe, il est possible de lui trouver une orientation forte en temps linéaire. En revanche, compter le nombre d'orientations fortes d'un graphe donné est un problème #P-complet.
Herbert Robbins présenta dans un article de 1939 la recherche d'une orientation forte par le problème d'une ville fictive dont les rues et les intersections sont représentés par un graphe G donné.
Pendant la semaine, les routes sont à double sens, mais la ville aimerait savoir si elle peut couper la circulation sur n'importe quelle section de rue pour y faire des travaux, tout en évitant qu'un quartier de la ville ne se retrouve inaccessible, c'est-à-dire qu'il doit toujours exister un itinéraire entre deux points de la ville, même si une section de rue est bloquée.
Le week-end, il n'y a pas de travaux et toutes les rues sont ouvertes à la circulation, mais pour réduire les embouteillages, la ville souhaiterait rendre toutes les rues à sens unique, toujours sans isoler un point de la ville du reste du réseau routier.
En termes de théorie des graphes, le critère des travaux en semaine peut être satisfait si G est un graphe sans pont (il est 2-arête-connexe) et celui des sens uniques du week-end est résolu s'il existe une orientation forte pour G.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.