Voir la source de 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{{sfnp|Robbins|1939}}, dit que les graphes qui possèdent une [[orientation forte]] sont exactement les [[Graphe arête-connexe|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 (mathématiques discrètes)|graphe non orienté]] {{Mvar|G}} pour le transformer en un graphe fortement connexe si et seulement si {{Mvar|G}} est [[Graphe connexe|connexe]] et n'a pas d'[[Isthme (théorie des graphes)|isthme]] :
: ''Un graphe non orienté admet une orientation qui le rend [[Graphe fortement connexe|fortement connexe]] si et seulement s'il est connexe sans isthme.''

Par ''orientation'' d'un graphe non orienté <math>G=(V, E)</math>, on entend un graphe orienté <math>G'= (V, E')</math> tel que pour chaque arête non orientée <math>\{v,u\} \in E</math>, exactement l'une des arêtes orientées <math>(v,u),(u,v)</math> est dans <math>E'</math>. 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<ref>C'est essentiellement sous cette forme qu'il est le Théorème 4.3.4. de {{harvsp|Bretto|Faisant|Hennecart|2012}}.</ref> :

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

Dans {{harvsp|Bretto|Faisant|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 [[multigraphe]]s{{sfnp|Boesch|Tindell|1980}} :

: ''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{{sfnp|Boesch|Tindell|1980}}.

Un tel graphe est connexe si, pour chaque paire de nœuds <math>u,v</math>, il existe un chemin allant de <math>u</math> à <math>v</math>, 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 [[Complexité en temps|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{{sfnp|Hopcroft|Tarjan|1973}} , elles sont orientées du descendant vers l'ancêtre. Il existe aussi des algorithmes parallèles pour résoudre le problème efficacement{{sfnp|Vishkin|1985}} et aussi pour trouver des orientations fortes de graphes mixtes{{sfnp|Soroker|1988}}.

== Motivation ==

Robbins{{sfnp|Robbins|1939}}  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é {{mvar|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 ==
*{{article
 | nom = Atallah | prénom = Mikhail J. | lien auteur = Mikhail Atallah
 | doi = 10.1016/0020-0190(84)90072-3
 | numéro = 1
 | journal = [[Information Processing Letters]]
 | mr = 742079
 | pages = 37–39
 | titre = Parallel strong orientation of an undirected graph
 | volume = 18
 | année = 1984| url = https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1361&context=cstech }}.
*{{ouvrage
 | nom = Balakrishnan | prénom = V. K.
 | chapitre = 4.6 Strong Orientation of Graphs
 | isbn = 978-0-486-69115-2
 | lieu = Mineola, NY
 | mr = 1402469
 | passage = 135
 | éditeur = Dover Publications Inc.
 | titre = Introductory Discrete Mathematics
 | url = https://books.google.com/books?id=pOBXUoVZ9EEC&pg=PA135
 | année = 1996}}.
*{{article
 | nom1 = Boesch | prénom1 = Frank
 | nom2 = Tindell | prénom2 = Ralph
 | doi = 10.2307/2321858
 | numéro = 9
 | journal = [[The American Mathematical Monthly]]
 | mr = 602828
 | pages = 716–719
 | titre = Robbins's theorem for mixed multigraphs
 | volume = 87
 | année = 1980| jstor = 2321858
 }}.
* {{Ouvrage
|auteur1= Alain Bretto | auteur2= Alain Faisant | auteur3 = François Hennecart
|titre= Éléments de théorie des graphes
|éditeur= Springer-Verlag France
|collection= IRIS
|lieu= Paris
|année= 2012
|pages totales= xix + 371
|passage= Théorème 4.3.4
|isbn= 978-2-8178-0280-0 |isbn2= 978-2-8178-0281-7
|zbl = 1250.68002
}}.
*{{ouvrage
 | nom1 = Gross | prénom1 = Jonathan L.
 | nom2 = Yellen | prénom2 = Jay
 | chapitre = Characterization of strongly orientable graphs
 | numéro édition = 2
 | isbn = 978-1-58488-505-4
 | lieu = Boca Raton, FL
 | mr = 2181153
 | passage = 498–499
 | pages totales =  xiv+779
 | éditeur = Chapman & Hall/CRC
 | collection = Discrete Mathematics and its Applications
 | titre = Graph Theory and its Applications
 | url = https://books.google.com/books?id=unEloQ_sYmkC&pg=PA498
 | année = 2006}}.
*{{article
 | nom1 = Hopcroft | prénom1 = John | lien auteur1 = John Hopcroft
 | nom2 = Tarjan | prénom2 = Robert | lien auteur2 = Robert Tarjan
 | doi = 10.1145/362248.362272
 | numéro = 6
 | journal = [[Communications of the ACM]]
 | pages = 372–378
 | titre = Algorithm 447: efficient algorithms for graph manipulation
 | volume = 16
 | année = 1973| s2cid = 14772567 }}.
*{{article
 | nom = Robbins | prénom = Herbert E. | lien auteur = Herbert Robbins
 | journal = [[American Mathematical Monthly]]
 | jstor = 2303897
 | pages = 281–283
 | titre = A theorem on graphs, with an application to a problem on traffic control
 | volume = 46
 | numéro = 5 | année = 1939
 | doi=10.2307/2303897}}.
*{{chapitre
 | nom = Roberts | prénom = Fred S. | lien auteur = Fred S. Roberts
 | titre = Chapter 2. The One-Way Street Problem
 | lieu = Philadelphia, Pa.
 | mr = 508050
 | passage = 7–14
 | éditeur = Society for Industrial and Applied Mathematics (SIAM)
 | collection = CBMS-NSF Regional Conference Series in Applied Mathematics |numéro dans collection = 29
 | titre ouvrage = Graph Theory and its Applications to Problems of Society
 | url = https://books.google.com/books?id=EYAwztXnzf8C&pg=PA7
 | année = 1978| isbn = 9780898710267 }}.
*{{article
 | nom = Soroker | prénom = Danny
 | numéro = 2
 | journal = Journal of Algorithms
 | mr = 936106
 | pages = 205–223
 | titre = Fast parallel strong orientation of mixed graphs and related augmentation problems
 | volume = 9
 | année = 1988
 | doi=10.1016/0196-6774(88)90038-7}}.
*{{article
 | nom = Vishkin | prénom = Uzi | lien auteur = Uzi Vishkin
 | doi = 10.1016/0020-0190(85)90025-0
 | numéro = 5
 | journal = [[Information Processing Letters]]
 | mr = 801988
 | pages = 235–240
 | titre = On efficient parallel strong orientation
 | volume = 20
 | année = 1985}}.

== Notes et références ==
{{Traduction/référence|de|Satz von Robbins|203946761}}
{{Références}}
{{Liens}}

{{portail|informatique théorique|mathématiques}}

[[Catégorie:Théorème de la théorie des graphes|Robbins]]