Ранг цикла

В теории графов циклический ранг ориентированного графа — это мера связности орграфа , впервые предложенная Эгганом и Бюхи (Eggan 1963). Интуитивно эта концепция измеряет, насколько орграф близок к ориентированному ациклическому графу (DAG), в том смысле, что DAG имеет циклический ранг нуль, в то время как полный орграф порядка n с самопетлей в каждой вершине имеет циклический ранг n . Циклический ранг ориентированного графа тесно связан с глубиной дерева неориентированного графа и с высотой звезды регулярного языка . Он также нашел применение в вычислениях разреженных матриц (см. Bodlaender et al. 1995) и логике (Rossman 2008).

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

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

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

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

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

Циклический ранг был введен Эгганом (1963) в контексте звездной высоты регулярных языков . Он был переоткрыт (Эйзенштат и Лю 2005) как обобщение ненаправленной глубины дерева , которая была разработана в начале 1980-х годов и применена к вычислениям разреженных матриц (Шрайбер 1982).

Циклический ранг направленного ациклического графа равен 0, в то время как полный орграф порядка n с самопетлей в каждой вершине имеет циклический ранг n . Помимо них, известен циклический ранг нескольких других орграфов: неориентированный путь порядка n , обладающий симметричным отношением ребра и не имеющий самопетлей, имеет циклический ранг (McNaughton 1969). Для направленного -тора , т. е. декартова произведения двух направленных контуров длин m и n , мы имеем и для m ≠ n (Eggan 1963, Gruber & Holzer 2008).${\displaystyle P_{n}}$${\displaystyle \lfloor \log n\rfloor }$${\displaystyle (м\раз n)}$${\displaystyle T_{м,н}}$${\displaystyle r(T_{n,n})=n}$${\displaystyle r(T_{m,n})=\min\{m,n\}+1}$

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

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

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

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

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

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

Доказательства этой теоремы были даны Эгганом (1963) и совсем недавно Сакаровичем (2009).

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

• Ранг в округе