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

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

Визначення

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

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

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

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

• Якщо $G$ не є компонентою сильної зв'язності, то $r(G)$ дорівнює найбільшому циклічному рангу серед усіх компонент сильної зв'язності графа $G$.

Деревна глибина неорієнтованого графа має дуже схоже визначення за допомогою неорієнтованої зв'язності та зв'язних компонентів замість сильної зв'язності та компонентів сильної зв'язності.

Історія

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

Приклади

Циклічний ранг спрямованого ациклічного графа дорівнює 0, тоді як повний орграф порядку n з петлею в кожній вершині має циклічний ранг n. Крім цих двох випадків, відомий циклічний ранг кількох інших орграфів: неорієнтований шлях $P_{n}$ порядку n, який має відношення симетрії ребер і не має петель, має циклічний ранг $\lfloor \log n\rfloor$. Для орієнтованого $(m\times n)$-тора $T_{m,n}$, тобто, прямого добутку двох орієнтованих контурів довжини m і n маємо $r(T_{n,n})=n$ і $r(T_{m,n})=\min\{m,n\}+1$ для m ≠ n.

Обчислення циклічного рангу

Обчислення циклічного рангу є складною задачею. Грубер довів, що відповідна задача розв'язності є NP-повною навіть для розріджених орграфів з найбільшим півстепенем виходу 2. Позитивним є те, що задача розв'язна за час $O(1.9129^{n})$ на орграфах з найбільшим напівстепенем виходу 2 і за час $O^{*}(2^{n})$ на загальних орграфах. Існує апроксимаційний алгоритм з коефіцієнтом апроксимації $O((\log n)^{\frac {3}{2}})$.

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

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

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

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

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

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

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

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

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

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

Див. також

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

Література

• 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 // 5th International Conference on Parallel Processing and Applied Mathematics. — 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 // Michigan Mathematical Journal. — 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 // Theoretical Computer Science. — 2012. — Vol. 14. — P. 189—204..
• Hermann Gruber, Markus Holzer. Finite automata, digraph connectivity, and regular expression size // Proc. 35th International Colloquium on Automata, Languages and Programming. — 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 // Journal of the ACM. — 2008. — Т. 55, вип. 3. — С. Article 15. — DOI:10.1145/1379759.1379763.
• Jacques Sakarovitch. Elements of Automata Theory. — Cambridge University Press, 2009. — ISBN 0-521-84425-8.
• Robert Schreiber. A new implementation of sparse Gaussian elimination // ACM Transactions on Mathematical Software. — 1982. — Т. 8, вип. 3. — С. 256—276. — DOI:10.1145/356004.356006. Архівовано з джерела 7 червня 2011.