Velosiped darajasi - Cycle rank

Yilda grafik nazariyasi, tsikl darajasi a yo'naltirilgan grafik a digraf ulanish birinchi bo'lib Eggan tomonidan taklif qilingan va Büchi (Eggan 1963 yil ). Ushbu kontseptsiya intuitiv ravishda adigrafning a ga qanchalik yaqinligini o'lchaydi yo'naltirilgan asiklik grafik (DAG), ya'ni DAG mototsiklining nol darajasi, a to'liq digraf ning buyurtma n bilan o'z-o'zidan halqa ateach vertex tsikl darajasiga ega n. Yo'naltirilgan grafaning tsikl darajasi quyidagilar bilan chambarchas bog'liq daraxt chuqurligi ning yo'naltirilmagan grafik va yulduz balandligi a oddiy til. Bundan tashqari, u useinni topdi siyrak matritsa hisoblashlar (qarang. qarang Bodlaender va boshq. 1995 yil ) va mantiq (Rossman 2008 yil ).

Ta'rif

Tsikl darajasi r(G) digrafning $G = (V, E)$ induktiv tarzda quyidagicha ta'riflanadi:

Agar G asiklikdir, keyin $r (G) = 0$ .
Agar G bu mustahkam bog'langan va E bo'sh emas, keyin

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

qayerda

{ displaystyle G-v}

vertexni yo'q qilish natijasida hosil bo'lgan digraf

v

va boshlanadigan yoki tugaydigan barcha qirralar

v

.

Agar G kuchli bog'langan emas, keyin r(G) ning barcha kuchli bog'langan tarkibiy qismlari orasidagi maksimal tsikl darajasiga teng G.

The daraxt chuqurligi yo'naltirilmagan grafika juda o'xshash ta'rifga ega, bu erda kuchli ulanish va kuchli bog'langan komponentlar o'rniga yo'naltirilmagan ulanish va ulangan komponentlar ishlatiladi.

Tarix

Velosiped darajasi martabali tomonidan kiritilgan Eggan (1963) kontekstida yulduz balandligi ning oddiy tillar. U tomonidan qayta kashf etilgan (Eisenstat va Liu 2005 yil ) yo'naltirilmaganni umumlashtirish sifatida daraxt chuqurligi, 1980-yillardan boshlab ishlab chiqilgan va amal qilgan siyrak matritsa hisoblashlar (Schreiber 1982 yil ).

Misollar

Yo'naltirilgan asiklik grafikning tsikli darajasi 0, tartibning to'liq digrafi esa n bilan o'z-o'zidan halqa ateach vertex tsikl darajasiga ega n. Ulardan tashqari, yana bir nechta digraflarning tsikli darajasi ma'lum: yo'naltirilmagan yo'l ${ displaystyle P_ {n}}$ tartib nnosimmetrik chekka munosabatiga ega va o'z-o'zidan halqalanmaydigan tsikl darajasiga ega ${ displaystyle lfloor log n rfloor}$ (McNaughton 1969 yil ). Yo'naltirilgan uchun ${ displaystyle (m marta n)}$ -torus ${ displaystyle T_ {m, n}}$ , ya'ni kartezian mahsuloti uzunlikdagi ikkita yo'naltirilgan sxemaning m va n, bizda ... bor ${ displaystyle r (T_ {n, n}) = n}$ va ${ displaystyle r (T_ {m, n}) = min {m, n } + 1}$ uchun m ≠ n (Eggan 1963 yil, Gruber va Xolzer 2008 yil ).

Tsikl darajasini hisoblash

Tsikl darajasini hisoblash juda qiyin: Gruber (2012) tegishli qaror muammosi ekanligini isbotlaydi To'liq emas, hatto maksimal darajadagi siyrak digraflar uchun ham 2. Ijobiy tomoni shundaki, muammo o'z vaqtida hal etiladi ${ displaystyle O (1.9129 ^ {n})}$ maksimal draflarda ustunlik ko'pi bilan 2 va o'z vaqtida ${ displaystyle O ^ {*} (2 ^ {n})}$ umumiy digraflarda. Bor taxminiy algoritm taxminiy nisbati bilan ${ displaystyle O (( log n) ^ { frac {3} {2}})}$ .

Ilovalar

Oddiy tillarning yulduz balandligi

Tsikl darajasining birinchi qo'llanilishi rasmiy til nazariyasi, o'rganish uchun yulduz balandligi ning oddiy tillar. Eggan (1963) doimiy iboralar, cheklangan avtomatlar va nazariyalar o'rtasidagi munosabatni o'rnatdi yo'naltirilgan grafikalar. Keyingi yillarda bu munosabat sifatida tanilgan Eggan teoremasi, qarang Sakarovich (2009). Avtomatika nazariyasida a n-harakatlari bilan nondeterministik cheklangan avtomat (b-NFA) a sifatida belgilanadi 5-karra, (Q, Σ, δ, q₀, F) dan iborat

cheklangan o'rnatilgan davlatlarning Q
cheklangan to'plam kirish belgilari Σ
belgilangan qirralarning to'plami δdeb nomlanadi o'tish munosabati: Q × (Σ ∪ {ε}) × Q. Bu erda the bo'sh so'z.
an boshlang'ich davlat q₀ ∈ Q
davlatlar majmui F sifatida ajratilgan qabul qiluvchi davlatlar F ⊆ Q.

Bir so'z w ∈ Σ^* a mavjud bo'lsa, b-NFA tomonidan qabul qilinadi yo'naltirilgan yo'l boshlang'ich holatidan q₀ ba'zi bir so'nggi holatga F dan qirralar yordamida δ, shunday qilib birlashtirish yo'l bo'ylab tashrif buyurgan barcha yorliqlarning so'zi w. Σ dan ortiq barcha so'zlar to'plami^* avtomat tomonidan qabul qilingan til avtomat tomonidan qabul qilingan A.

Nondeterministik cheklangan avtomatning digraf xususiyatlari haqida gapirganda A davlat to'plami bilan Q, biz tabiiy ravishda vertikal to'plam bilan digrafga murojaat qilamiz Q uning o'tish munosabati bilan qo'zg'atilgan. Endi teorema quyidagicha bayon etilgan.

Eggan teoremasi: Oddiy tilning yulduz balandligi L hamma orasida minimal tsikl darajasiga teng ε-harakatlari bilan nondeterministik cheklangan avtomatlar qabul qilish L.

Ushbu teoremaning isboti tomonidan berilgan Eggan (1963), va yaqinda tomonidan Sakarovich (2009).

Matritsani siyrak hisoblashda xoleskiy faktorizatsiya

Ushbu kontseptsiyaning yana bir qo'llanilishi yotadi siyrak matritsa hisoblashlar, ya'ni ishlatish uchun ichki ajratish hisoblash Xoleskiy faktorizatsiya parallel (nosimmetrik) matritsaning Berilgan siyrak ${ displaystyle (n marta n)}$ -matrisa M ba'zi nosimmetrik digraflarning qo'shni matritsasi sifatida talqin qilinishi mumkin G kuni n matritsaning nolga teng bo'lmagan yozuvlari chekkalari bilan bittadan yozishmalarda bo'ladigan tarzda G. Agar digrafning tsikl darajasi bo'lsa G ko'pi bilan k, keyin Cholesky faktorizatsiyasi M eng ko'p hisoblash mumkin k bilan parallel kompyuterda qadamlar ${ displaystyle n}$ protsessorlar (Dereniowski & Kubale 2004 yil ).

Shuningdek qarang

O'chirish darajasi

Adabiyotlar

Bodlaender, Xans L.; Gilbert, Jon R.; Xafsteynsson, Xalmtir; Kloks, Ton (1995), "Kenglik, yo'lning kengligi, frontsize va eng qisqa eliminatsiya daraxtini yaqinlashtirish", Algoritmlar jurnali, 18 (2): 238–255, doi:10.1006 / jagm.1995.1009, Zbl 0818.68118^{[doimiy o'lik havola ]}.
Dereniovskiy, Dariush; Kubale, Marek (2004), "Matritsalarning xoleskiy faktorizatsiyasi va grafikalar reytingi", Parallel ishlov berish va amaliy matematika bo'yicha 5-xalqaro konferentsiya (PDF), Kompyuter fanlari bo'yicha ma'ruzalar, 3019, Springer-Verlag, 985–992 betlar, doi:10.1007/978-3-540-24669-5_127, Zbl 1128.68544, dan arxivlangan asl nusxasi (PDF) 2011-07-16.
Eggan, Lourens S (1963), "O'tish grafikalari va muntazam hodisalarning yulduz balandligi", Michigan matematik jurnali, 10 (4): 385–397, doi:10.1307 / mmj / 1028998975, Zbl 0173.01504.
Eyzenstat, Stenli S.; Liu, Jozef V. H. (2005), "siyrak simmetrik matritsalar uchun daraxtlarni yo'q qilish nazariyasi", Matritsalarni tahlil qilish va qo'llash bo'yicha SIAM jurnali, 26 (3): 686–705, doi:10.1137 / S089547980240563X.
Gruber, Hermann (2012), "Rasmiy til nazariyasidagi murakkablik o'lchovlari va qo'llanmalari" (PDF), Diskret matematika va nazariy kompyuter fanlari, 14 (2): 189–204.
Gruber, German; Xoltser, Markus (2008), "Sonlu avtomatika, digraf ulanishi va muntazam ifodaning o'lchami" (PDF), Proc. Avtomatika, tillar va dasturlash bo'yicha 35-xalqaro kollokvium, Kompyuter fanlari bo'yicha ma'ruzalar, 5126, Springer-Verlag, 39-50 betlar, doi:10.1007/978-3-540-70583-3_4.
McNaughton, Robert (1969), "Doimiy tadbirlarning halqaviy murakkabligi", Axborot fanlari, 1 (3): 305–328, doi:10.1016 / S0020-0255 (69) 80016-2.
Rossman, Benjamin (2008), "Gomomorfizmni saqlash teoremalari", ACM jurnali, 55 (3): 15-modda, doi:10.1145/1379759.1379763.
Sakarovich, Jak (2009), Avtomatika nazariyasining elementlari, Kembrij universiteti matbuoti, ISBN 0-521-84425-8
Shrayber, Robert (1982), "Gausslarni yo'q qilishning yangi tatbiqi" (PDF), Matematik dasturiy ta'minot bo'yicha ACM operatsiyalari, 8 (3): 256–276, doi:10.1145/356004.356006, dan arxivlangan asl nusxasi (PDF) 2011-06-07 da, olingan 2010-01-04.