Циклический ранг

Циклический ранг r(G) орграфа G = (V, E) индуктивно определяется следующим образом

• Если G ацикличен, то r(G) = 0.
• Если G сильно связан и E не пусто, то

${\displaystyle r(G)=1+\min _{v\in V}r(G-v),\,}$ где ${\displaystyle G-v}$ является орграфом, полученным удалением вершины v и всех рёбер, начинающихся или оканчивающихся в v.

• Если G не является компонентой сильной связности, то r(G) равен максимальному циклическому рангу среди всех компонент сильной связности графа 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}})}$.

• Контурный ранг