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, 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 : Un graphe admet une orientation forte si et seulement s'il est 2-arête connexe. Dans , 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 : 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. 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.