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^[1]. 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

${\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.

Histoire

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

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 ${\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].

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

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 ${\displaystyle n}$ processeurs (Dereniowski & Kubale 2004^[9]).

Notes et références

1. (en) Eggan, Lawrence C., « Transition graphs and the star-height of regular events », Michigan Mathematical Journal,‎ 1963, p. 385–397
2. (en) Eisenstat, Stanley C et Liu, Joseph W. H., « The theory of elimination trees for sparse unsymmetric matrices », The theory of elimination trees for sparse unsymmetric matrices,‎ 2005, p. 686-705
3. (en) Schreiber, Robert, « A new implementation of sparse Gaussian elimination », ACM Transactions on Mathematical Software,‎ 1982, p. 256-276 (lire en ligne)
4. (en) McNaughton, Robert, « The loop complexity of regular events », Information Sciences,‎ 1969, p. 305-328
5. (en) Gruber, Hermann et Holzer, Markus, « Finite automata, digraph connectivity, and regular expression size », International Colloquium on Automata, Languages and Programming,‎ 2008, p. 39-50
6. (en) Gruber, Hermann, « Digraph Complexity Measures and Applications in Formal Language Theory », Discrete Mathematics & Theoretical Computer Science,‎ 2012, p. 189-204 (lire en ligne)
7. (en) Eggan, Lawrence C., « Transition graphs and the star-height of regular events », Michigan Mathematical Journal,‎ 1963, p. 385–397 (lire en ligne)
8. (en) Sakarovitch, Jacques, Elements of Automata Theory, Cambridge University Press, 2009 (ISBN 0-521-84425-8)
9. (en) Dereniowski, Dariusz et Kubale, Marek, « Cholesky Factorization of Matrices in Parallel and Ranking of Graphs », Lecture Notes on Computer Science,‎ 2004, p. 985–992 (lire en ligne)

• Portail des mathématiques