Циклічний ранг

Циклічний ранг орієнтованого графа — міра зв'язності орграфа, яку запропонували Егган і ^[en]. Це поняття інтуїтивно відбиває, наскільки близький орграф до спрямованого ациклічного графа (САГ, англ. DAG), коли циклічний ранг САГ дорівнює нулю, тоді як повний орграф порядку n із петлями в кожній вершині має циклічний ранг n. Циклічний ранг орієнтованого графа тісно пов'язаний із деревною глибиною неорієнтованого графа та висотою ітерації регулярних мов. Циклічний ранг набув застосування в обчисленнях із розрідженими матрицями (див. статтю Bodlaender, Gilbert, Hafsteinsson, Kloks, 1995) та логіці.

Визначення

Циклічний ранг ${\displaystyle r(G)}$ орграфа G = (V, E) індуктивно визначається так:

• Якщо ${\displaystyle G}$ ациклічний, то r(G) = 0 .
• Якщо ${\displaystyle G}$ сильно зв'язний і ${\displaystyle E}$ не порожня, то

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

де ${\displaystyle G-v}$ — орграф, отриманий видаленням вершини ${\displaystyle v}$ і всіх ребер, що починаються або закінчуються в ${\displaystyle v}$.

• Якщо ${\displaystyle G}$ не є компонентою сильної зв'язності, то ${\displaystyle r(G)}$ дорівнює найбільшому циклічному рангу серед усіх компонент сильної зв'язності графа ${\displaystyle 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}})}$.

Застосування

Висота ітерації регулярних мов

Циклічний ранг вперше застосовано в теорії формальних мов для вивчення висоти ітерації регулярних мов. Егган установив відношення між теоріями регулярних виразів, скінченними автоматами та орієнтованими графами. Пізніше це відношення стало відомим як теорема Еггана. У теорії автоматів недетермінований скінченний автомат з ε-переходами (ε-НСА) визначається як 5-ка, (Q, Σ δ q₀ F), що складається з:

• скінченної множини станів Q,
• скінченної множини вхідних символів Σ,
• множини помічених дуг δ, званих переходами : ${\displaystyle Q\times (\Sigma \cup \{\varepsilon \})\times Q}$ (тут ε позначає порожній рядок),
• початкового стану q₀ ∈ Q,
• множини станів F, званих поглинальними, F⊆Q.

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

Якщо говорити про недетермінований скінченний автомат A зі множиною станів Q як про орієнтований граф, ми природно маємо на увазі граф із множиною вершин Q, породженою переходами.

Теорема Еггана: Висота ітерації регулярної мови L дорівнює найменшому циклічному рангу серед усіх недетермінованих скінченних автоматів з ε-переходами, що приймають мову L.

Докази цієї теореми дали Егган і пізніше Сакарович .

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

Інше застосування цієї концепції лежить в галузі обчислень з розрідженими матрицями, а саме, для використання ^[en] при обчисленні розкладу Холецького (симетричної) матриці за допомогою паралельного алгоритму. Задану розріджену ${\displaystyle (n\times n)}$ матрицю M можна інтерпретувати як матрицю суміжності деякого симетричного орграфа G з n вершинами, так що ненульові елементи матриці відповідають один до одного ребрам графа G. Якщо циклічний ранг орграфа G не перевищує k, то на паралельному комп'ютері з ${\displaystyle n}$ процесорами розклад Холецького матриці M можна обчислити за не більше ніж k кроків.

Див. також

• Контурний ранг
• Ранг (теорія графів)

Примітки

1. Eggan, 1963.
2. Rossman, 2008.
3. Eisenstat, Liu, 2005.
4. Schreiber, 1982.
5. McNaughton, 1969.
6. Gruber, Holzer, 2008.
7. Gruber, 2012.
8. Sakarovitch, 2009.
9. Dereniowski, Kubale, 2004.

Література

• Hans L. Bodlaender, John R. Gilbert, Hjálmtýr Hafsteinsson, Ton Kloks. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree // Journal of Algorithms. — 1995. — Т. 18, вип. 2. — С. 238—255. — DOI:10.1006/jagm.1995.1009.
• Dariusz Dereniowski, Marek Kubale. Cholesky Factorization of Matrices in Parallel and Ranking of Graphs // . — Springer-Verlag, 2004. — Т. 3019. — С. 985—992. — (Lecture Notes on Computer Science) — DOI:10.1007/978-3-540-24669-5_127..
• Lawrence C. Eggan. Transition graphs and the star-height of regular events // . — 1963. — Т. 10, вип. 4. — С. 385—397. — DOI:10.1307/mmj/1028998975.
• Stanley C. Eisenstat, Joseph W. H. Liu. The theory of elimination trees for sparse unsymmetric matrices // SIAM Journal on Matrix Analysis and Applications. — 2005. — Т. 26, вип. 3. — С. 686—705. — DOI:10.1137/S089547980240563X.
• Hermann Gruber. Digraph Complexity Measures and Applications in Formal Language Theory // ^[en]. — 2012. — Vol. 14. — P. 189—204..
• Hermann Gruber, Markus Holzer. Finite automata, digraph connectivity, and regular expression size // . — Springer-Verlag, 2008. — Т. 5126. — С. 39—50. — (Lecture Notes on Computer Science) — DOI:10.1007/978-3-540-70583-3_4.
• Robert McNaughton. The loop complexity of regular events // Information Sciences. — 1969. — Т. 1, вип. 3. — С. 305—328. — DOI:10.1016/S0020-0255(69)80016-2.
• Benjamin Rossman. Homomorphism preservation theorems // . — 2008. — Т. 55, вип. 3. — С. Article 15. — DOI:10.1145/1379759.1379763.
• Jacques Sakarovitch. Elements of Automata Theory. — Cambridge University Press, 2009. — .
• Robert Schreiber. A new implementation of sparse Gaussian elimination // . — 1982. — Т. 8, вип. 3. — С. 256—276. — DOI:10.1145/356004.356006. з джерела 7 червня 2011.