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

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

Визначення

Циклічний ранг ${\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}$.

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

Історія

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

Приклади

Циклічний ранг спрямованого ациклічного графа дорівнює 0, тоді як повний орграф порядку n з петлею в кожній вершині має циклічний ранг n. Крім цих двох випадків, відомий циклічний ранг кількох інших орграфів: неорієнтований шлях ${\displaystyle P_{n}}$ порядку n, який має відношення симетрії ребер і не має петель, має циклічний ранг ${\displaystyle \lfloor \log n\rfloor }$^[5]. Для орієнтованого ${\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^[1][6].

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

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

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

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

Циклічний ранг вперше застосовано в теорії формальних мов для вивчення висоти ітерації регулярних мов. Егган^[1] установив відношення між теоріями регулярних виразів, скінченними автоматами та орієнтованими графами. Пізніше це відношення стало відомим як теорема Еггана^[8]. У теорії автоматів недетермінований скінченний автомат з ε-переходами (ε-НСА) визначається як 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.

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

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

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

Див. також

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