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

Определение

Циклический ранг 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 .

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

История

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

Примеры

Циклический ранг направленного ациклического графа равен 0, в то время как полный орграф порядка n с петлёй в каждой вершине имеет циклический ранг n . Кроме этих двух случаев, известен циклический ранг нескольких других орграфов: неориентированный путь ${\displaystyle P_{n}}$ порядка n , который обладает отношением симметрии рёбер и не имеет петель, имеет циклический ранг ${\displaystyle \lfloor \log n\rfloor }$ . Для ориентированного ${\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 .

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

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

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

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

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

См. также

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

Примечания

Литература