Ранг цикла

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

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

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

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

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

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

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

История [ править ]

Цикл разряд был введен Eggan (1963) в контексте высоты звезды на регулярных языках . Он был переоткрыт ( Eisenstat & Liu 2005 ) как обобщение неориентированного древовидного метода , который был разработан с 1980-х годов и применен к вычислениям разреженных матриц ( Schreiber 1982 ).

Примеры [ править ]

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

Вычисление ранга цикла [ править ]

Вычисление ранга цикла является вычислительно трудным: Gruber (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
• конечный набор входных символов Σ
• множество ребер помечены & delta ; , называется переходным соотношением : Q × (E ∪ {ε}) × Q . Здесь ε обозначает пустое слово .
• начальное состояние д ₀ ∈ Q
• множество состояний Р отличаются , как допускающие состояния F ⊆ Q .

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

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

Eggan по теореме : звезда высота обычного языка L равен ранг минимального цикла среди всех недетерминированных конечных автоматов с й-ходами приема L .

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

Факторизация Холецкого в вычислениях разреженных матриц [ править ]

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

См. Также [ править ]

• Рейтинг цепи

Ссылки [ править ]