Orientation forte

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^[1]. 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.

Exemple du réseau routier[modifier | modifier le code]

Herbert Robbins présenta dans un article de 1939^[2] 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. Le théorème de Robbins (ou théorème des sens uniques^[3]) affirme qu'un réseau routier satisfait le problème des travaux si et seulement si il résout celui des sens uniques.

À la suite des travaux de Robbins, une série d'articles de Roberts et Xu^[4],[5] modélisa le problème sur un réseau routier en grille, par exemple dans une ville ayant adopté un plan en damier. En examinant la transformation de rues à double sens en rues à sens unique, et les effets de cette transformation sur les distances entre les paires de points au sein de la grille, ils démontrèrent que la disposition habituelle des sens uniques dans laquelle les rues parallèles alternent en direction n'est pas optimale pour minimiser la distance entre deux points quelconques de la ville. Cependant, les orientations de rues proposées dans l'article incluent des points où le trafic provenant de deux blocs à sens unique se rencontre de front, ce qui est un inconvénient d'un point de vue pratique.

Cas particuliers[modifier | modifier le code]

Un graphe eulérien non orienté est toujours fortement orientable. En effet, une orientation eulérienne du graphe, construite en choisissant un sens de parcours pour le circuit eulérien et en orientant chaque arête dans le sens parcouru, est toujours une orientation forte^[6]. De plus, dans une orientation eulérienne, le degré entrant est égal au degré sortant pour chaque sommet.

Un théorème de Nash-Williams^[7] déclare qu'il existe pour tout graphe non orienté G une orientation bien équilibrée . Une orientation est bien équilibrée si, pour toute paire de sommets u et v dans G, il existe dans le graphe orienté résultant au moins ${\displaystyle \lfloor {\frac {k}{2}}\rfloor }$ chemins de u à v dont les arêtes sont deux à deux disjointes ; où k est le nombre maximum de chemins dans l'ensemble des chemins de u à v du graphe non orienté à arêtes disjointes. Les orientations de Nash-Williams ont également la propriété d'être aussi proches que possible des orientations eulériennes : le degré entrant et le degré sortant de chaque sommet diffèrent au plus de 1.

L'existence d'orientations bien équilibrées et le théorème de Menger, impliquent immédiatement le théorème de Robbins. D'après le théorème de Menger, un graphe 2-arête-connexe (i.e. sans pont) a au moins deux chemins d'arêtes disjointes entre chaque paire de sommets, d'où il suit que tout graphe orienté par une orientation bien équilibrée doit être fortement connexe. Plus généralement, ce résultat implique que chaque graphe 2k-arêtes-connexe peut être orienté pour former un graphe orienté k-arête-connexe.

Une orientation totalement cyclique d'un graphe G est une orientation dans laquelle chaque arête appartient à un cycle orienté. Pour un graphe connexe, cette notion est équivalente à l'orientation forte, mais des orientations totalement cycliques peuvent également être définies pour les graphes non connexes. Dans ce cas, chaque composante connexe de G devient fortement connexe sous cette orientation.

Le théorème de Robbins peut être reformulé comme affirmant qu'un graphe (non nécessairement connexe) peut être orienté par une orientation totalement cyclique si et seulement s'il n'a pas de pont.

Les orientations totalement cycliques sont duales aux orientations acycliques (orientations qui transforment G en un graphe acyclique orienté ) en ce sens que, si G est un graphe planaire et que les orientations de G sont transférées aux orientations du graphe planaire dual de G en tournant chaque arête 90 degrés dans le sens des aiguilles d'une montre, alors une orientation totalement cyclique de G correspond ainsi à une orientation acyclique du graphe dual et vice-versa^[8],[9]. Le nombre d'orientations totalement cycliques distinctes d'un graphe G est T_G(0,2) où T_G est le polynôme de Tutte du graphe, et par dualité, le nombre d'orientations acycliques est T_G(2,0)^[10] . En conséquence, le théorème de Robbins implique que le polynôme de Tutte a une racine au en (0,2) si et seulement si le graphe G a un pont.

Si, pour une orientation forte, tous les cycles orientés passent par une seule arête st (autrement dit, si il existe une arête dont le changement de sens produit une orientation acyclique) alors l'orientation acyclique formée en réalisant le changement sens de st est une orientation bipolaire. Chaque orientation bipolaire est ainsi liée à une orientation forte^[11].

Flip graphs[modifier | modifier le code]

Si G est un graphe 3-arête-connexe et que X et Y sont deux orientations fortes différentes de G, alors il est possible de transformer X en Y en changeant l'orientation des arêtes unes par une, de telle sorte qu'à chaque étape, l'orientation du graphe reste forte^[12]. Par conséquent, le flip graph dont les sommets correspondent aux orientations fortes de G, et dont les arêtes correspondent à des paires d'orientations fortes qui diffèrent dans la direction d'une seule arête, forme un cube partiel.

Algorithmes et complexité[modifier | modifier le code]

Une orientation forte d'un graphe non orienté sans pont quelconque peut être établie en temps linéaire en effectuant un parcours en profondeur du graphe. On oriente d'abord toutes les arêtes de l'arbre obtenu dans le sens allant d'un nœud parent vers ses enfants (les branches s'éloignant de la racine de l'arbre). Enfin, on oriente toutes les arêtes restantes (qui sont nécessairement entre un ancêtre et un descendant dans l'arbre de recherche en profondeur) du descendant à l'ancêtre (c'est-à-dire en se rapprochant de la racine).

Pour un graphe non orienté G ayant des ponts, si l'on donne une liste de paires ordonnées de sommets qui doivent être connectés par des chemins orientés, il est possible de trouver en temps polynomial une orientation de G qui relie toutes les paires données, si une telle orientation existe. Cependant, le même problème est NP-complet lorsque l'entrée peut être un graphe mixte^[13].

Compter le nombre d'orientations fortes d'un graphe G donné est un problème #P-complet même lorsque G est planaire et biparti. Cependant, pour les graphes denses (plus précisément, les graphes dans lesquels chaque sommet a un nombre O(n) de voisins), le nombre d'orientations fortes peut être estimé par un schéma d'approximation aléatoire entièrement polynomial^[8],[14]. Le problème du comptage des orientations fortes peut également être résolu exactement, en temps polynomial, pour des graphes dont la largeur arborescente est bornée^[8].

Références[modifier | modifier le code]

• Portail de l'informatique théorique