Rang cyclique (graphe orienté)

En théorie des graphes, le rang cyclique d'un graphe orienté est une mesure de la connexité introduite par Eggan et Büchi en 1963. Intuitivement, cette valeur mesure à quel point un graphe est presque acyclique : un graphe orienté acyclique a un rang cyclique de zéro, tandis qu'un digraphe complet d'ordre n (avec une boucle à chaque sommet) a un rang cyclique n. Le rang cyclique d'un graphe orienté est proche de la hauteur d'étoile des langages rationnels.

Définition

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

$r(G)=1+\min _{v\in V}r(G-v),\,$ où $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.

Histoire

Le rang cyclique a été introduit par Eggan pour résoudre le problème de la hauteur d'étoile des langages rationnels. Il a été ensuite redécouvert par Eisenstat et Liu 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.

Exemples

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 $Pn$ de n sommets à double sens a un rang cyclique de $\lfloor \log n\rfloor$ .
• 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 $r(T_{m,n})=\min\{m,n\}+1$ si m ≠ n.

Calculer le rang cyclique

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. On peut trouver une solution en temps en $O(1.9129^{n})$ sur des graphes orientés de degré au plus 2^{[réf. nécessaire]}, et en temps en $O^{*}(2^{n})$ en général^{[réf. nécessaire]}. Il existe un algorithme d'approximation de ratio en $O((\log n)^{\frac {3}{2}})$^{[réf. nécessaire]}.

Applications

La hauteur d'étoile des langages rationnels

La première application du rang cyclique fut en théorie des langages formels, afin d'étudier la hauteur d'étoile des langages rationnels. Eggan (1963) établit une relation entre la théorie des expressions régulières, des automates finis et des graphes orientés. Dans les années qui suivirent, cette relation devint connue sous le nom du Théorème d'Eggan, cf. Sakarovitch (2009). Dans la théorie des automates, un automate fini non-déterministe avec ε-transitions (ε-AFN) est défini par un 5-uplet (Q, Σ, δ, q₀, F) où

• Q est un ensemble fini d'états
• Σ est un ensemble fini de lettres
• δ est un ensemble d'arcs orientés étiquetés par des lettres, représenté par une partie de Q × (Σ∪{ε}) × Q où ε représente le mot vide
• q₀ ∈ Q est l'état initial
• F ⊆ Q est l'ensemble des états finaux ou états acceptants

Un mot m ∈ Σ^* est accepté par l'ε-AFN si, et seulement si, il existe un chemin de l'état initial q₀ à un état final de F n'utilisant que des arcs de δ et de sorte que la concaténation de toutes les étiquettes visitées au long du chemin forme le mot m. L'ensemble des mots de Σ^* acceptés par l'automate est le langage accepté par l'automate. Un automate fini non-déterministe peut être vu comme un graphe orienté dont les sommets sont les états Q et dont les arcs sont les transitions de δ.

Ainsi s'énonce le théorème :

Théorème d'Eggan : La hauteur d'étoile d'un langage rationnel L est égale au rang cyclique minimum parmi tous les automates finis non-déterministes avec ε-transitions acceptant L.

La preuve de ce théorème est donnée dans Eggan (1963), et plus récemment dans Sakarovitch (2009).

Factorisation de Cholesky dans le calcul des matrices creuses

Une autre application de ce concept appartient au domaine du calcul des matrices creuses, plus précisément pour utiliser la dissection imbriquée pour calculer la factorisation de Cholesky d'une matrice (symétrique) en parallèle. Une matrice M creuse carrée de taille n peut être interprétée comme la matrice d'adjacence d'un graphe orienté G symétrique ayant n sommets, de sorte que les coefficients non-nuls de la matrice correspondent exactement aux arcs de G. Si le rang cyclique du graphe orienté G est au plus k, alors la factorisation de Cholesky de M peut être calculée en au plus k étapes sur un ordinateur parallèle disposant de $n$ processeurs (Dereniowski & Kubale 2004).