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

Циклічний ранг орієнтованого графа — міра зв'язності орграфа, яку запропонували Егган і Шаблон:Не перекладеноШаблон:Sfn. Це поняття інтуїтивно відбиває, наскільки близький орграф до спрямованого ациклічного графа (САГ, Шаблон:Lang-en), коли циклічний ранг САГ дорівнює нулю, тоді як повний орграф порядку n із петлями в кожній вершині має циклічний ранг n. Циклічний ранг орієнтованого графа тісно пов'язаний із деревною глибиною неорієнтованого графа та висотою ітерації регулярних мов. Циклічний ранг набув застосування в обчисленнях із розрідженими матрицями (див. статтю Шаблон:Harvnb) та логіціШаблон:Sfn.

Визначення

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

• Якщо $G$ ациклічний, то Шаблон:Math .
• Якщо $G$ сильно зв'язний і $E$ не порожня, то

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

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

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

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

Історія

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

Приклади

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Література

• Шаблон:Стаття
• Шаблон:Книга.
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття.
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття