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

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

ОпределениеПравить

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

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

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

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

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

ИсторияПравить

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

ПримерыПравить

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

Вычисление циклического рангаПравить

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

ПриложенияПравить

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

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

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

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

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

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

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

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

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

См. такжеПравить

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