Цикл дәрежесі - Cycle rank

Жылы графтар теориясы, цикл дәрежесі а бағытталған граф Бұл диграф қосылым алдымен Эгган ұсынған шара Бючи (Eggan 1963 ). Интуитивті түрде бұл тұжырымдама а-ге қаншалықты жақын екенін өлшейді бағытталған ациклдік график (DAG), мағынасы бойынша, DAG велосипедтің нөлдік дәрежесі, ал a толық диграф туралы тапсырыс n а өзіндік цикл ateach шыңында цикл дәрежесі бар n. Бағытталған графиктің цикл дәрежесі -мен тығыз байланысты ағаштың тереңдігі туралы бағытталмаған граф және жұлдыз биіктігі а тұрақты тіл. Ол сондай-ақ усеин тапты сирек матрица есептеу (қараңыз. қараңыз) Bodlaender және басқалар. 1995 ж ) және логика (Россман 2008 ж ).

Анықтама

Цикл дәрежесі р(G) диграфтың $G = (V, E)$ индуктивті түрде келесідей анықталады:

Егер G ациклді болып табылады $р (G) = 0$ .
Егер G болып табылады қатты байланысты және E онда бос емес

{ displaystyle r (G) = 1 + min _ {v in V} r (G-v), ,}

қайда

{ displaystyle G-v}

- бұл шыңды жою нәтижесінде пайда болған диграф

v

және басталатын немесе аяқталатын барлық шеттер

v

.

Егер G тығыз байланысты емес, содан кейін р(G) -ның барлық тығыз байланысты компоненттерінің арасындағы циклдің максималды дәрежесіне тең G.

The ағаштың тереңдігі Бағытталмаған графиктің анықтамасы өте ұқсас, бұл бағытталмаған қосылымды және байланысқан компоненттерді мықты байланыс пен мықты байланысқан компоненттердің орнына қолданады.

Тарих

Цикл дәрежесі енгізілді Эгган (1963) контекстінде жұлдыз биіктігі туралы қарапайым тілдер. Оны қайта ашты (Eisenstat & Liu 2005 ж ) бағытталмаған жалпылау ретінде ағаштың тереңдігі, 1980-ші жылдардың басында әзірленген және оған қатысты сирек матрица есептеулер (Шрайбер 1982 ж ).

Мысалдар

Бағытталған ациклдік графиктің циклдік деңгейі 0-ге тең, ал реттік толық диграф n а өзіндік цикл ateach шыңында цикл дәрежесі бар n. Бұлардан басқа бірнеше диграфтардың циклдік дәрежесі белгілі: бағытталмаған жол ${ displaystyle P_ {n}}$ тәртіп nсимметриялы шеткі қатынасқа ие және өзіндік циклсыз цикл дәрежесіне ие ${ displaystyle lfloor log n rfloor}$ (McNaughton 1969 ). Режиссер үшін ${ displaystyle (m рет n)}$ -торус ${ displaystyle T_ {m, n}}$ , яғни декарттық өнім ұзындықтың екі бағытталған тізбегінің м және n, Бізде бар ${ displaystyle r (T_ {n, n}) = n}$ және ${ displaystyle r (T_ {m, n}) = min {m, n } + 1}$ үшін m ≠ n (Eggan 1963, Gruber & Holzer 2008 ).

Цикл дәрежесін есептеу

Цикл дәрежесін есептеу өте қиын: Грубер (2012) шешімнің сәйкес проблемасы екенін дәлелдейді NP аяқталды, тіпті максималды дәреженің сирек диграфтары үшін де. Оң жағынан, мәселе уақыт бойынша шешіледі ${ displaystyle O (1.9129 ^ {n})}$ максимум диграфтарында жоғары дәреже ең көбі 2, уақыт өте келе ${ displaystyle O ^ {*} (2 ^ {n})}$ жалпы диграфтарда. Бар жуықтау алгоритмі жуықтау коэффициентімен ${ displaystyle O (( log n) ^ { frac {3} {2}})}$ .

Қолданбалар

Кәдімгі тілдердің жұлдызды биіктігі

Цикл дәрежесінің алғашқы қолданылуы болды ресми тіл теориясы, оқуға арналған жұлдыз биіктігі туралы қарапайым тілдер. Эгган (1963) тұрақты өрнектер, ақырлы автоматтар және теориялары арасындағы байланысты орнатты бағытталған графиктер. Кейінгі жылдары бұл қатынас белгілі болды Эгган теоремасы, сал. Сакарович (2009). Автоматтар теориясында а ε жүрісі бар шектелмеген автоматты (ε-NFA) ретінде анықталады 5 кортеж, (Q, Σ, δ, q₀, F) тұрады

ақырлы орнатылды мемлекеттердің Q
ақырлы жиынтығы енгізу белгілері Σ
белгіленген шеттер жиынтығы δдеп аталады өтпелі қатынас: Q × (Σ ∪ {ε}) × Q. Мұнда the бос сөз.
ан бастапқы мемлекет q₀ ∈ Q
мемлекеттер жиынтығы F ретінде ерекшеленеді қабылдаушы күйлер F ⊆ Q.

Сөз w ∈ Σ^* бар болса, ε-NFA қабылдайды бағытталған жол бастапқы күйден q₀ соңғы жағдайға дейін F шеттерін пайдаланып δ, сияқты тізбектеу жол бойында қаралған барлық белгілер сөз береді w. Барлық сөздердің жиынтығы Σ^* автоматы қабылдаған болып табылады тіл автомат қабылдады A.

Шектелмеген автоматты диграфтық қасиеттер туралы айтқанда A мемлекеттік жиынтығымен Q, біз диграфты табиғи түрде шыңдар жиынтығымен шешеміз Q оның өтпелі қатынасымен туындаған. Енді теорема келесідей айтылды.

Эгган теоремасы: Кәдімгі тілдің жұлдыз биіктігі L барлығының арасындағы ең төменгі цикл деңгейіне тең ε жүрісі бар шектелмеген автоматтар қабылдау L.

Бұл теореманың дәлелдері келтірілген Эгган (1963), және жақында Сакарович (2009).

Матрицалық сирек есептеулердегі холеск факторизациясы

Бұл тұжырымдаманың тағы бір қолданылуы сирек матрица есептеу, дәлірек айтсақ пайдалану үшін ішіне кесу есептеу үшін Холески факторизациясы (симметриялы) матрицаның параллель. Берілген сирек ${ displaystyle (n рет n)}$ -матрица М кейбір симметриялық диграфтың іргелес матрицасы ретінде түсіндірілуі мүмкін G қосулы n матрицаның нөлдік емес жазбалары шеттерімен бір-біріне сәйкес келетін етіп шыңдар G. Егер диграфтың циклдік дәрежесі болса G ең көп дегенде к, содан кейін Холески факторизациясы М ең көбі есептелуі мүмкін к параллель компьютердегі қадамдар ${ displaystyle n}$ процессорлар (Dereniowski & Kubale 2004 ж ).

Сондай-ақ қараңыз

Электр тізбегі

Әдебиеттер тізімі

Бодлаендер, Ханс Л.; Гилберт, Джон Р .; Хафстейнссон, Хальмтыр; Kloks, Ton (1995), «Жақтаудың ені, ені, фронтальды және ең қысқа жою ағашы», Алгоритмдер журналы, 18 (2): 238–255, дои:10.1006 / jagm.1995.1009, Zbl 0818.68118^{[тұрақты өлі сілтеме ]}.
Дерениовский, Дариуш; Кубале, Марек (2004), «Матрицалардың параллельді және графиктік рейтингідегі холестериндік факторизациясы», Параллельді өңдеу және қолданбалы математика бойынша 5-ші халықаралық конференция (PDF), Информатика бойынша дәрістер, 3019, Springer-Verlag, 985–992 б., дои:10.1007/978-3-540-24669-5_127, Zbl 1128.68544, мұрағатталған түпнұсқа (PDF) 2011-07-16.
Эгган, Лоуренс С. (1963), «Өтпелі графиктер және тұрақты оқиғалардың жұлдызды биіктігі», Michigan Mathematical Journal, 10 (4): 385–397, дои:10.1307 / mmj / 1028998975, Zbl 0173.01504.
Эйзенстат, Стэнли С .; Лю, Джозеф В. Х. (2005), «Сирек симметриялы матрицалар үшін ағаштарды жою теориясы», Матрицалық анализ және қосымшалар туралы SIAM журналы, 26 (3): 686–705, дои: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.
McNaughton, Роберт (1969), «Тұрақты іс-шаралардың күрделі күрделілігі», Ақпараттық ғылымдар, 1 (3): 305–328, дои:10.1016 / S0020-0255 (69) 80016-2.
Россман, Бенджамин (2008), «Гомоморфизмді сақтау теоремалары», ACM журналы, 55 (3): 15-бап, дои:10.1145/1379759.1379763.
Сакарович, Жак (2009), Автоматтар теориясының элементтері, Кембридж университетінің баспасы, ISBN 0-521-84425-8
Шрайбер, Роберт (1982), «Гауссты сирек жоюдың жаңа бағдарламасы» (PDF), Математикалық бағдарламалық жасақтамадағы ACM транзакциялары, 8 (3): 256–276, дои:10.1145/356004.356006, мұрағатталған түпнұсқа (PDF) 2011-06-07, алынды 2010-01-04.