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

Multigraphes

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.

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é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.

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 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].

Motivation

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

• Mikhail J. Atallah, « Parallel strong orientation of an undirected graph », Information Processing Letters, vol. 18, n^o 1,‎ 1984, p. 37–39 (DOI 10.1016/0020-0190(84)90072-3, MR 742079, lire en ligne).
• V. K. Balakrishnan, Introductory Discrete Mathematics, Mineola, NY, Dover Publications Inc., 1996 (ISBN 978-0-486-69115-2, MR 1402469, lire en ligne), « 4.6 Strong Orientation of Graphs », p. 135.
• Frank Boesch et Ralph Tindell, « Robbins's theorem for mixed multigraphs », The American Mathematical Monthly, vol. 87, n^o 9,‎ 1980, p. 716–719 (DOI 10.2307/2321858, JSTOR 2321858, MR 602828).
• Alain Bretto, Alain Faisant et François Hennecart, Éléments de théorie des graphes, Paris, Springer-Verlag France, coll. « IRIS », 2012, xix + 371 (ISBN 978-2-8178-0280-0 et 978-2-8178-0281-7, zbMATH 1250.68002), Théorème 4.3.4.
• Jonathan L. Gross et Jay Yellen, Graph Theory and its Applications, Boca Raton, FL, Chapman & Hall/CRC, coll. « Discrete Mathematics and its Applications », 2006, 2^e éd., xiv+779 (ISBN 978-1-58488-505-4, MR 2181153, lire en ligne), « Characterization of strongly orientable graphs », p. 498–499.
• John Hopcroft et Robert Tarjan, « Algorithm 447: efficient algorithms for graph manipulation », Communications of the ACM, vol. 16, n^o 6,‎ 1973, p. 372–378 (DOI 10.1145/362248.362272, S2CID 14772567).
• Herbert E. Robbins, « A theorem on graphs, with an application to a problem on traffic control », American Mathematical Monthly, vol. 46, n^o 5,‎ 1939, p. 281–283 (DOI 10.2307/2303897, JSTOR 2303897).
• Fred S. Roberts, « Chapter 2. The One-Way Street Problem », dans Graph Theory and its Applications to Problems of Society, Philadelphia, Pa., Society for Industrial and Applied Mathematics (SIAM), coll. « CBMS-NSF Regional Conference Series in Applied Mathematics » (n^o 29), 1978 (ISBN 9780898710267, MR 508050, lire en ligne), p. 7–14.
• Danny Soroker, « Fast parallel strong orientation of mixed graphs and related augmentation problems », Journal of Algorithms, vol. 9, n^o 2,‎ 1988, p. 205–223 (DOI 10.1016/0196-6774(88)90038-7, MR 936106).
• Uzi Vishkin, « On efficient parallel strong orientation », Information Processing Letters, vol. 20, n^o 5,‎ 1985, p. 235–240 (DOI 10.1016/0020-0190(85)90025-0, MR 801988).

Notes et références

• (de) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en allemand intitulé « Satz von Robbins » (voir la liste des auteurs).

1. Robbins (1939).
2. C'est essentiellement sous cette forme qu'il est le Théorème 4.3.4. de Bretto, Faisant et Hennecart 2012.
3. Boesch et Tindell (1980).
4. Hopcroft et Tarjan (1973).
5. Vishkin (1985).
6. Soroker (1988).