Ранг цикла

В теории графов цикловый ранг — ориентированного графа это орграфа, мера связности впервые предложенная Эгганом и Бючи ( Eggan 1963 ). Интуитивно эта концепция измеряет, насколько близкоорграф относится к ориентированному ациклическому графу (DAG) в том смысле, что DAG имеетцикл нулевого ранга, а орграф порядка n полный с петлей в точкекаждая вершина имеет циклический ранг n . Ранг цикла ориентированного графа тесно связан с глубиной дерева неориентированного графа и высотой звезды регулярного языка . Он также нашел применениев с разреженной матрицей вычислениях (см. Bodlaender et al. 1995 ) и логике ( Россман 2008 ).

Определение

Ранг цикла 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. компонентов

Глубина дерева неориентированного графа имеет очень похожее определение: в нем используются ненаправленная связность и связные компоненты вместо сильной связности и сильно связных компонентов.

История

Ранг цикла был введен Эгганом (1963) в контексте высоты звезды регулярных языков . Он был заново открыт ( Eisenstat & Liu 2005 ) как обобщение ненаправленной глубины дерева , которое разрабатывалось начиная с 1980-х годов.и применяется для с разреженными матрицами вычислений ( Шрайбер, 1982 ).

Примеры

Циклический ранг ориентированного ациклического графа равен 0, а полного орграфа порядка n с петлей в точкекаждая вершина имеет циклический ранг n . Помимо них, известен циклический ранг еще нескольких орграфов: ненаправленный путь $P_{n}$ порядка n , который обладает симметричным реберным отношением и не имеет петель, имеет цикловый ранг $\lfloor \log n\rfloor$ ( Макнотон, 1969 ). Для направленного $(m\times n)$ -тор $T_{m,n}$ , т. е. декартово произведение двух направленных цепей длин m и n , имеем $r(T_{n,n})=n$ и $r(T_{m,n})=\min\{m,n\}+1$ для m ≠ n ( Эгган 1963 , Грубер и Хольцер 2008 ).

Вычисление ранга цикла

Вычисление ранга цикла сложно с вычислительной точки зрения: Грубер (2012) доказывает, что соответствующая проблема решения является NP-полной даже для разреженных орграфов с максимальной исходящей степенью не более 2. С положительной стороны, проблема разрешима за время. $O(1.9129^{n})$ на орграфах максимальной исходящей степени не более 2, а по времени $O^{*}(2^{n})$ по общим орграфам. Существует алгоритм аппроксимации с коэффициентом аппроксимации $O((\log n)^{\frac {3}{2}})$ .

Приложения

Звездная высота обычных языков

Первое применение циклического ранга было в формальной теории языков для изучения звездной высоты регулярных языков . Эгган (1963) установил связь между теориями регулярных выражений, конечных автоматов и ориентированных графов . В последующие годы это соотношение стало известно как теорема Эггана , ср. Сакарович (2009) . В теории автоматов недетерминированный конечный автомат с ε-ходами -NFA) определяется как набор из 5 элементов ( Q , Σ, δ , q0 _, ( ε F ), состоящий из

конечное множество состояний Q
конечное множество входных символов Σ
набор помеченных ребер δ , называемый отношением перехода : Q × (Σ ∪{ε}) Q. × Здесь ε обозначает пустое слово .
начальное состояние q ₀ ∈ Q
набор состояний F, отличающихся как принимающие состояния F ⊆ Q .

Слово w ∈ Σ ^* принимается ε-NFA, если существует направленный путь от начального состояния q ₀ до некоторого конечного состояния в F с использованием ребер из δ , такой, что объединение всех меток, посещенных по пути, дает слово w . Множество всех слов над Σ ^* принимаемый автоматом — это язык принимаемый автоматом A. ,

Говоря о свойствах орграфа недетерминированного конечного автомата A с множеством состояний Q , мы естественно обращаемся к орграфу с множеством вершин Q, индуцированным его отношением перехода. Теперь теорема формулируется следующим образом.

Теорема Эггана : Звездная высота регулярного языка L равна минимальному рангу цикла среди всех недетерминированных конечных автоматов с ε-ходами допускающими L. ,

Доказательства этой теоремы даны Эгганом (1963) , а совсем недавно Сакаровичем (2009) .

Факторизация Холецкого в вычислениях с разреженной матрицей

Другое применение этой концепции заключается в вычислениях с разреженной матрицей , а именно для использования вложенного рассечения вычисления факторизации Холецкого для параллельного (симметричной) матрицы. Данный разреженный $(n\times n)$ -матрица M может интерпретироваться как матрица смежности некоторого симметричного орграфа G на n вершинах таким образом, что ненулевые элементы матрицы находятся во взаимно однозначном соответствии с краями G . Если цикловый ранг орграфа G не превышает k , то факторизация Холецкого M может быть вычислена не более чем за k шагов на параллельном компьютере с $n$ процессоры ( Деренёвски и Кубале, 2004 ).

См. также

Ранг цепи

Ссылки

Бодлендер, Ханс Л .; Гилберт, Джон Р.; Хафстейнссон, Хьялмтир; Клокс, Тон (1995), «Аппроксимация ширины дерева, ширины пути, фронтального размера и кратчайшего дерева исключения», Journal of Algorithms , 18 (2): 238–255, doi : 10.1006/jagm.1995.1009 , Zbl 0818.68118 .
Деренёвский, Дариуш; Кубале, Марек (2004), «Факторизация матриц Холецкого в параллельном режиме и ранжирование графов», 5-я Международная конференция по параллельной обработке и прикладной математике (PDF) , Конспекты лекций по информатике, том. 3019, Springer-Verlag, стр. 985–992, номер документа : 10.1007/978-3-540-24669-5_127 , ISBN. 978-3-540-21946-0 , Zbl 1128.68544 , заархивировано из оригинала (PDF) 16 июля 2011 г.
Эгган, Лоуренс К. (1963), «Графы переходов и высота звезды регулярных событий», Michigan Mathematical Journal , 10 (4): 385–397, doi : 10.1307/mmj/1028998975 , Zbl 0173.01504 .
Эйзенштат, Стэнли К.; Лю, Джозеф WH (2005), «Теория деревьев исключения для разреженных несимметричных матриц», SIAM Journal on Matrix Analysis and Applications , 26 (3): 686–705, doi : 10.1137/S089547980240563X .
Грубер, Герман (2012), «Меры сложности орграфов и их приложения в теории формального языка» (PDF) , Дискретная математика и теоретическая информатика , 14 (2): 189–204 .
Грубер, Герман; Хольцер, Маркус (2008), «Конечные автоматы, связность орграфов и размер регулярного выражения» (PDF) , Proc. 35-й Международный коллоквиум по автоматам, языкам и программированию , Конспекты лекций по информатике, том. 5126, Springer-Verlag, стр. 39–50, номер документа : 10.1007/978-3-540-70583-3_4 , ISBN. 978-3-540-70582-6 .
Макнотон, Роберт (1969), «Петлевая сложность регулярных событий», Information Sciences , 1 (3): 305–328, doi : 10.1016/S0020-0255(69)80016-2 .
Россман, Бенджамин (2008), «Теоремы сохранения гомоморфизма», Журнал ACM , 55 (3): Статья 15, doi : 10.1145/1379759.1379763 .
Сакарович, Жак (2009), Элементы теории автоматов , Cambridge University Press, ISBN 978-0-521-84425-3
Шрайбер, Роберт (1982), «Новая реализация разреженного исключения Гаусса» (PDF) , ACM Transactions on Mathematical Software , 8 (3): 256–276, doi : 10.1145/356004.356006 , заархивировано из оригинала (PDF) в 2011 г. -06-07 , получено 4 января 2010 г.