Rang cyclique (graphe orienté)

Le rang cyclique r(G) d'un graphe orienté G = (V, E) est défini par induction sur le nombre de sommets dans G :

• Si G est acyclique, alors r(G) = 0.
• Si G est fortement connexe et E non vide, alors

${\displaystyle r(G)=1+\min _{v\in V}r(G-v),\,}$ où ${\displaystyle G-v}$ est le graphe orienté obtenu en supprimant le sommet v et toutes les arêtes qui commencent ou terminent au sommet v.

• Si G n'est pas fortement connexe, alors r(G) est égal au maximum des rangs cycliques des composantes fortement connexes de G.

Le rang cyclique a été introduit par Eggan[1] pour résoudre le problème de la hauteur d'étoile des langages rationnels. Il a été ensuite redécouvert par Eisenstat et Liu[2] par généralisation de la notion de profondeur d'arbre pour les graphes non orientés, qui a été développée et appliquée aux calculs de matrices creuses dans les années 80[3].

Le rang cyclique d'un graphe orienté acyclique est 0, et un graphe complet à n sommets (avec, en plus une arête allant de chaque sommet à lui-même) a un rang cyclique de n. Le rang cyclique de quelques autres graphes est connu :

• Le chemin ${\displaystyle Pn}$ de n sommets à double sens a un rang cyclique de ${\displaystyle \lfloor \log n\rfloor }$[4] .
• Le produit cartésien du cycle à n sommets et du cycle à m sommets (c’est-à-dire le tore à m lignes et n colonnes) est n si m ≠ n et ${\displaystyle r(T_{m,n})=\min\{m,n\}+1}$ si m ≠ n[1] - [5].

Le calcul du rang cyclique est un problème algorithmique complexe. Le problème de décision est NP-complet, même pour des graphes orientés de degré 2[6]. On peut trouver une solution en temps en ${\displaystyle O(1.9129^{n})}$ sur des graphes orientés de degré au plus 2, et en temps en ${\displaystyle O^{*}(2^{n})}$ en général. Il existe un algorithme d'approximation de ratio en ${\displaystyle O((\log n)^{\frac {3}{2}})}$.