Цикл ранга

редактировать

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

Содержание

1 Определение
2 История
3 Примеры
4 Вычисление ранга цикла
5 Приложения
- 5.1 Высота звезды регулярных языков
- 5.2 Факторизация Холецкого в разреженной матрице вычисления
6 См. также
7 Ссылки

Определение

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

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

r (G) = 1 + min v ∈ V r ( G - v), {\ displaystyle r (G) = 1 + \ min _ {v \ in V} r (Gv), \,}

r (G) = 1 + \ min _ {{v \ in V}} r (Gv), \,

где

G - v {\ displaystyle Gv}

{\ displaystyle Gv}

- орграф, полученный в результате удаления вершины v и всех ребер, начинающихся или заканчивающихся в v.

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

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

История

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

Примеры

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

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

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

Приложения

Звездная высота обычных языков

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

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

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

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

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

Доказательства этой теоремы даются Eggan (1963), а позднее - Sakarovitch (2009).

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

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

См. Также

Рейтинг цепи

Ссылки