Théorème de Robbins

Summarize Timeline Fact Check

Le théorème dit qu'il est possible d'orienter les arêtes d'un graphe non orienté G pour le transformer en un graphe fortement connexe si et seulement si G 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é ${\displaystyle G=(V,E)}$, on entend un graphe orienté ${\displaystyle G'=(V,E')}$ tel que pour chaque arête non orientée ${\displaystyle \{v,u\}\in E}$, exactement l'une des arêtes orientées ${\displaystyle (v,u),(u,v)}$ est dans ${\displaystyle E'}$. 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^[2] :

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

Dans Bretto, Faisant et Hennecart 2012, 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.

Le théorème peut être généralisé aux multigraphes^[3] :

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

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ées^[3].

Un tel graphe est connexe si, pour chaque paire de nœuds ${\displaystyle u,v}$, il existe un chemin allant de ${\displaystyle u}$ à ${\displaystyle 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.

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 parcours^[4] , elles sont orientées du descendant vers l'ancêtre. Il existe aussi des algorithmes parallèles pour résoudre le problème efficacement^[5] et aussi pour trouver des orientations fortes de graphes mixtes^[6].