Théorème de Robbins — Wikipédia

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.

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é , on entend un graphe orienté tel que pour chaque arête non orientée , exactement l'une des arêtes orientées est dans . 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

[modifier | modifier le code]

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

[modifier | modifier le code]

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 , il existe un chemin allant de à , 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é

[modifier | modifier le code]

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

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

[modifier | modifier le code]

Notes et références

[modifier | modifier le code]
  1. a et b 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. a et b Boesch et Tindell (1980).
  4. Hopcroft et Tarjan (1973).
  5. Vishkin (1985).
  6. Soroker (1988).