Théorème de Robbins

En théorie des graphes, le théorème de Robbins, nommé d'après Herbert Robbins qui l'a formulé en 1939Modèle:Sfnp, dit que les graphes qui possèdent une orientation forte sont exactement les graphes connexes sans isthme ou graphes 2-arête-connexes.

Énoncés

Graphes

Le théorème dit qu'il est possible d'orienter les arêtes d'un graphe non orienté Modèle:Mvar pour le transformer en un graphe fortement connexe si et seulement si Modèle:Mvar est connexe et n'a pas d'isthme :

Un graphe non orienté admet une orientation qui le rend fortement connexe si et seulement s'il est connexe sans isthme.

Par orientation d'un graphe non orienté $G=(V,E)$, on entend un graphe orienté $G^{\prime }=(V,E^{\prime })$ tel que pour chaque arête non orientée $\{v,u\}\in E$, exactement l'une des arêtes orientées $(v,u),(u,v)$ est dans $E^{\prime }$. Une orientation forte est, en théorie des graphes, l'attribution d'un sens à chaque arête d'un graphe non orienté qui en fait un graphe fortement connexe. Ainsi, le théorème peut s'énoncer aussi :

Un graphe admet une orientation forte si et seulement s'il est connexe sans isthme.

Enfin, un graphe est 2-arête-connexe s'il faut enlever au moins 2 arêtes pour le déconnecter. Ceci est équivalent à la propriété d'être connexe sans isthme. Le théorème s'énonce donc également :

Un graphe admet une orientation forte si et seulement s'il est 2-arête connexe.

Dans Modèle:Harvsp, les auteurs appellent « orientable » un graphe qui admet une orientation forte. Et leur théorème 4.3.4.dit en effet que

Un graphe est orientable si et seulement s'il est 2-arête connexe.

Multigraphes

Le théorème peut être généralisé aux multigraphesModèle:Sfnp :

Un multigraphe admet une orientation forte si et seulement s'il est 2-arête connexe.

Graphes mixtes

Boesch et Tindell ont étendu le théorème de Robbins aux graphes mixtes : ce sont des graphes qui contiennent à la fois des arêtes orientées et non orientéesModèle:Sfnp.

Un tel graphe est connexe si, pour chaque paire de nœuds $u,v$, il existe un chemin allant de $u$ à $v$, qui respecte les arêtes orientées : les arêtes orientées ne peuvent être utilisées que dans la direction donnée. Dans ce cas aussi, on a :

Un multigraphe mixte possède une orientation forte si et seulement s'il est 2-arête connexe.

Algorithmes et complexité

Une orientation forte d'un graphe connexe non orienté sans isthme donné peut être calculée en temps linéaire en effectuant un parcours en profondeur du graphe ; dans ce parcours, on oriente les arêtes sur l'arbre du parcours depuis la racine de l'arbre ; les arêtes restantes qui doivent nécessairement connecter un ancêtre et un descendant dans l'arbre parcoursModèle:Sfnp , elles sont orientées du descendant vers l'ancêtre. Il existe aussi des algorithmes parallèles pour résoudre le problème efficacementModèle:Sfnp et aussi pour trouver des orientations fortes de graphes mixtesModèle:Sfnp.

Motivation

RobbinsModèle:Sfnp illustre le problème de l'orientation forte avec une ville, dont les rues et les intersections sont représentées par un graphe donné Modèle:Mvar. Selon Robbins, les habitants de la ville veulent être en mesure de réparer un segment de route pendant les jours ouvrables de la semaine, tout en permettant d'atteindre toute partie de la ville de toute autre en utilisant les routes restantes comme des rues à double sens. Le week-end, toutes les routes sont ouvertes, mais en raison de l'importance du trafic, ils souhaitent convertir toutes les routes en sens unique et tout en conservant l'accessibilité. Le théorème de Robbins stipule qu'un système de routes est adapté aux réparations en semaine si et seulement s'il est adapté à la conversion en système à sens unique le week-end.

Bibliographie

• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Article.
• Modèle:Article.
• Modèle:Chapitre.
• Modèle:Article.
• Modèle:Article.