Циклический ранг

Циклический ранг ориентированного графа — мера связности орграфа, предложенная Эгганом и Бучи^{[англ.][1]}. Это понятие интуитивно отражает, насколько близок орграф к направленному ациклическому графу (НАГ, en:DAG), когда циклический ранг НАГ равен нулю, в то время как ориентированный орграф порядка n с петлями в каждой вершине имеет циклический ранг n. Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой итерации регулярных языков. Циклический ранг нашёл применение также в вычислениях с разреженными матрицами (см. статью Bodlaender, Gilbert, Hafsteinsson, Kloks, 1995) и логике^[2].

Определение

Циклический ранг r(G) орграфа G = (V, E) индуктивно определяется следующим образом

• Если G ацикличен, то r(G) = 0.
• Если G сильно связан и E не пусто, то

${\displaystyle r(G)=1+\min _{v\in V}r(G-v),\,}$ где ${\displaystyle G-v}$ является орграфом, полученным удалением вершины v и всех рёбер, начинающихся или оканчивающихся в v.

• Если G не является компонентой сильной связности, то r(G) равен максимальному циклическому рангу среди всех компонент сильной связности графа G.

Глубина дерева неориентированного графа имеет очень похожее определение с помощью неориентированной связности и связных компонент вместо сильной связности и компонент сильной связности.

История

Циклический ранг ввёл Эгган^[1] в контексте высоты итерации регулярных языков. Циклический ранг переоткрыли Айзенштат и Лю^[3] как обобщение неориентированной глубины дерева. Понятие разрабатывалось с начала 1980-х и применялось для работы с разреженными матрицами^[4].

Примеры

Циклический ранг направленного ациклического графа равен 0, в то время как полный орграф порядка n с петлёй в каждой вершине имеет циклический ранг n. Кроме этих двух случаев, известен циклический ранг нескольких других орграфов: неориентированный путь ${\displaystyle P_{n}}$ порядка n, который обладает отношением симметрии рёбер и не имеет петель, имеет циклический ранг ${\displaystyle \lfloor \log n\rfloor }$^[5]. Для ориентированного ${\displaystyle (m\times n)}$-тора ${\displaystyle T_{m,n}}$, т.е. прямого произведения двух ориентированных контуров длины m и n, имеем ${\displaystyle r(T_{n,n})=n}$ и ${\displaystyle r(T_{m,n})=\min\{m,n\}+1}$ для m ≠ n^[1][6].

Вычисление циклического ранга

Вычисление циклического ранга является сложной задачей. Грубер^[7] доказал, что соответствующая задача разрешимости является NP-полной даже для разреженных орграфов с максимальной полустепенью исхода 2. Положительный момент состоит в том, что задача разрешима за время ${\displaystyle O(1.9129^{n})}$ на орграфах с максимальной полустепенью исхода 2 и за время ${\displaystyle O^{*}(2^{n})}$ на общих орграфах. Существует аппроксимационный алгоритм с аппроксимационным коэффициентом ${\displaystyle O((\log n)^{\frac {3}{2}})}$.

Приложения

Высота итерации регулярных языков

Первое приложение циклического ранга было в теории формальных языков для изучения высоты итерации языка регулярных языков. Эгган^[1] установил отношение между теориями регулярных выражений, конечными автоматами и ориентированными графами. В последующих годах это отношение стало известно как теорема Эггана^[8]. В теории автоматов недетерминированный конечный автомат с ε-переходами (ε-НКА) определяется как 5-ка, (Q, Σ, δ, q₀, F), состоящая из

• конечного множества состояний Q
• конечного множества входных символов Σ (алфавита)
• множества помеченных рёбер δ, называемых отношениями перехода: Q × (Σ ∪{ε}) × Q. Здесь ε означает пустую строку.
• начального состояния q₀ ∈ Q
• множества состояний F (поглощающие состояния) F ⊆ Q.

Слово w ∈ Σ^* допускается ε-НКА автоматом, если существует ориентированный путь из начального состояния q₀ в некоторое конечное состояние из F используя рёбра из δ, так что конкатенация всех меток вдоль пути даёт слово w. Множество всех слов над Σ^*, допускаемых автоматом, является языком, принимаемым автоматом A.

Когда говорят о свойствах орграфов недетерминированного конечного автомата A с множеством состояний Q, естественным образом подразумевается орграф с множеством вершин Q, порождённый отношением переходов.

Теорема Эггана: Высота итерации языка регулярного языка L равна минимальному циклическому рангу среди всех недетерминированных конечных автоматов c ε-переходами (с пустыми переходами), принимающих язык L.

Доказательства этой теоремы дали Эгган^[1] и, позднее, Сакарович^[8].

Разложение Холецкого для разреженных матриц

Другое приложение этой концепции лежит в области вычислений с разреженными матрицами, а именно, для использования вложенного рассечения^[англ.] при вычислении разложения Холецкого (симметричной) матрицы с помощью параллельного алгоритма. Заданную разреженную ${\displaystyle (n\times n)}$ матрицу M можно интерпретировать как матрицу смежности некоторого симметричного орграфа G с n вершинами, так что ненулевые элементы матрицы соответствуют один-к-одному рёбрам графа G. Если циклический ранг орграфа G не превосходит k, то разложение Холецкого матрицы M может быть вычислено максимум за k шагов на параллельном компьютере с ${\displaystyle n}$ процессорами^[9].

См. также

• Контурный ранг

Примечания

1. Eggan, 1963.
2. Rossman, 2008.
3. Eisenstat, Liu, 2005.
4. Schreiber, 1982.
5. McNaughton, 1969.
6. Gruber, Holzer, 2008.
7. Gruber, 2012.
8. Sakarovitch, 2009.
9. Dereniowski, Kubale, 2004.

Литература

• Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, Ton Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree // Journal of Algorithms. — 1995. — Т. 18, вып. 2. — С. 238—255. — doi:10.1006/jagm.1995.1009.
• Dariusz Dereniowski, Marek Kubale. Cholesky Factorization of Matrices in Parallel and Ranking of Graphs // 5th International Conference on Parallel Processing and Applied Mathematics. — Springer-Verlag, 2004. — Т. 3019. — С. 985—992. — (Lecture Notes on Computer Science). — doi:10.1007/978-3-540-24669-5_127..
• Lawrence C. Eggan. Transition graphs and the star-height of regular events // Michigan Mathematical Journal. — 1963. — Т. 10, вып. 4. — С. 385—397. — doi:10.1307/mmj/1028998975.
• Stanley C. Eisenstat, Joseph W. H. Liu. The theory of elimination trees for sparse unsymmetric matrices // SIAM Journal on Matrix Analysis and Applications. — 2005. — Т. 26, вып. 3. — С. 686—705. — doi:10.1137/S089547980240563X.
• Hermann Gruber. Digraph Complexity Measures and Applications in Formal Language Theory (англ.) // Theoretical Computer Science^[англ.]. — 2012. — Vol. 14. — P. 189—204..
• Hermann Gruber, Markus Holzer. Finite automata, digraph connectivity, and regular expression size // Proc. 35th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 2008. — Т. 5126. — С. 39—50. — (Lecture Notes on Computer Science). — doi:10.1007/978-3-540-70583-3_4.
• Robert McNaughton. The loop complexity of regular events // Information Sciences. — 1969. — Т. 1, вып. 3. — С. 305—328. — doi:10.1016/S0020-0255(69)80016-2.
• Benjamin Rossman. Homomorphism preservation theorems // Journal of the ACM. — 2008. — Т. 55, вып. 3. — С. Article 15. — doi:10.1145/1379759.1379763.
• Jacques Sakarovitch. Elements of Automata Theory. — Cambridge University Press, 2009. — ISBN 0-521-84425-8.
• Robert Schreiber. A new implementation of sparse Gaussian elimination // ACM Transactions on Mathematical Software. — 1982. — Т. 8, вып. 3. — С. 256—276. — doi:10.1145/356004.356006. Архивировано 7 июня 2011 года.