Циклічний ранг орієнтованого графа — міра зв'язності орграфа, яку запропонували Егган і . Це поняття інтуїтивно відбиває, наскільки близький орграф до спрямованого ациклічного графа (САГ, ), коли циклічний ранг САГ дорівнює нулю, тоді як повний орграф порядку n із петлями в кожній вершині має циклічний ранг n. Циклічний ранг орієнтованого графа тісно пов'язаний із деревною глибиною неорієнтованого графа та висотою ітерації регулярних мов. Циклічний ранг набув застосування в обчисленнях із розрідженими матрицями (див. статтю ) та логіці.
Визначення Циклічний ранг орграфа індуктивно визначається так:
Якщо ациклічний, то . Якщо сильно зв'язний і не порожня, то
де — орграф, отриманий видаленням вершини і всіх ребер, що починаються або закінчуються в .
Якщо не є компонентою сильної зв'язності, то дорівнює найбільшому циклічному рангу серед усіх компонент сильної зв'язності графа .
Деревна глибина неорієнтованого графа має дуже схоже визначення за допомогою неорієнтованої зв'язності та зв'язних компонентів замість сильної зв'язності та компонентів сильної зв'язності.
Історія Циклічний ранг увів Егган у контексті висоти ітерації регулярних мов. Айзенштат і Лю перевідкрили циклічний ранг як узагальнення неорієнтованої деревної глибини. Поняття розроблялося від початку 1980-х і застосовувалося до роботи з розрідженими матрицями.
Приклади Циклічний ранг спрямованого ациклічного графа дорівнює 0, тоді як повний орграф порядку n з петлею в кожній вершині має циклічний ранг n. Крім цих двох випадків, відомий циклічний ранг кількох інших орграфів: неорієнтований шлях порядку n, який має відношення симетрії ребер і не має петель, має циклічний ранг . Для орієнтованого -тора , тобто, прямого добутку двох орієнтованих контурів довжини m і n маємо і для m ≠ n.
Обчислення циклічного рангу Обчислення циклічного рангу є складною задачею. Грубер довів, що відповідна задача розв'язності є NP-повною навіть для розріджених орграфів з найбільшим півстепенем виходу 2. Позитивним є те, що задача розв'язна за час на орграфах з найбільшим напівстепенем виходу 2 і за час на загальних орграфах. Існує апроксимаційний алгоритм з коефіцієнтом апроксимації .
Застосування
Висота ітерації регулярних мов Циклічний ранг вперше застосовано в теорії формальних мов для вивчення висоти ітерації регулярних мов. Егган установив відношення між теоріями регулярних виразів, скінченними автоматами та орієнтованими графами. Пізніше це відношення стало відомим як теорема Еггана. У теорії автоматів недетермінований скінченний автомат з ε-переходами (ε-НСА) визначається як 5-ка, (Q, Σ δ q0 F), що складається з:
скінченної множини станів Q, скінченної множини вхідних символів Σ, множини помічених дуг δ, званих переходами : (тут ε позначає порожній рядок), початкового стану q0 ∈ Q, множини станів F, званих поглинальними, F⊆Q.
ε-НСА приймає слово w ∈ Σ*, якщо існує орієнтований ланцюг із початкового стану q0 до деякого кінцевого стану F, що використовує дуги з δ так що конкатенація всіх міток уздовж шляху утворює слово w. Множина всіх слів над Σ*, які приймає автомат, є мовою, яку приймає автомат A.
Якщо говорити про недетермінований скінченний автомат A зі множиною станів Q як про орієнтований граф, ми природно маємо на увазі граф із множиною вершин Q, породженою переходами.
Теорема Еггана: Висота ітерації регулярної мови L дорівнює найменшому циклічному рангу серед усіх недетермінованих скінченних автоматів з ε-переходами, що приймають мову L.
Докази цієї теореми дали Егган і пізніше Сакарович .
Розклад Холецького для розріджених матриць Інше застосування цієї концепції лежить в галузі обчислень з розрідженими матрицями, а саме, для використання при обчисленні розкладу Холецького (симетричної) матриці за допомогою паралельного алгоритму. Задану розріджену матрицю M можна інтерпретувати як матрицю суміжності деякого симетричного орграфа G з n вершинами, так що ненульові елементи матриці відповідають один до одного ребрам графа G. Якщо циклічний ранг орграфа G не перевищує k, то на паралельному комп'ютері з процесорами розклад Холецького матриці M можна обчислити за не більше ніж k кроків.
Див. також Контурний ранг Ранг (теорія графів)
Примітки
Література
.
.