Tranzitiv pasayish - Transitive reduction

Yilda matematika, a o'tish davri kamayishi a yo'naltirilgan grafik D. bir xil tepaliklarga ega va imkon qadar kam qirralarga ega bo'lgan yana bir yo'naltirilgan grafik, masalan, agar tepadan (yo'naltirilgan) yo'l bo'lsa v tepaga w yilda D., keyin kamaytirishda ham shunday yo'l bor. Tranzitiv qisqartirishlar joriy etildi Aho, Garey va Ullman (1972), ularni qurishning hisoblash murakkabligi bo'yicha qat'iy chegaralarni ta'minlagan.

Texnik jihatdan qisqartirish bir xil bo'lgan yo'naltirilgan grafikadir erishish imkoniyati kabi munosabat D.. Teng ravishda, D. va uning o'tish davri qisqarishi bir xil bo'lishi kerak o'tish davri yopilishi bir-birlari kabi va uning o'tish davri kamayishi ushbu xususiyatga ega bo'lgan barcha grafikalar orasida imkon qadar kam qirralarga ega bo'lishi kerak.

Sonli transitiv kamayish yo'naltirilgan asiklik grafik (yo'naltirilgan tsikllarsiz yo'naltirilgan grafik) noyob va a subgraf berilgan grafikaning Shu bilan birga, (yo'naltirilgan) tsiklli grafikalar uchun noyoblik muvaffaqiyatsizlikka uchraydi va cheksiz grafikalar uchun hatto mavjudligi kafolatlanmaydi.

A ning chambarchas bog'liq tushunchasi minimal teng grafik ning subgrafasi D. bir xil erishish imkoniyatiga ega va imkon qadar kam qirralar.[1] Farqi shundaki, tranzitiv reduksiya subgrafasi bo'lishi shart emas D.. Sonli yo'naltirilgan asiklik grafikalar uchun minimal ekvivalent grafik tranzitiv kamayish bilan bir xil. Biroq, tsikllarni o'z ichiga olishi mumkin bo'lgan grafikalar uchun minimal teng grafikalar mavjud Qattiq-qattiq o'tish uchun qisqartirishlarni yaratish mumkin polinom vaqti.

Tranzitiv qisqartirish mavhum uchun belgilanishi mumkin ikkilik munosabat a o'rnatilgan, munosabatlar juftlarini yo'naltirilgan grafada yoy sifatida talqin qilish orqali.

Asiklik yo'naltirilgan grafikalarda

Sonli transitiv kamayish yo'naltirilgan grafik G bir xil bo'lgan eng kichik qirralarning grafigi erishish imkoniyati munosabatlar asl grafik sifatida. Ya'ni, agar tepadan yo'l bo'lsa x tepaga y grafada G, yo'l ham bo'lishi kerak x ga y ning o'tish davri qisqarishida Gva aksincha. Quyidagi rasmda tranzitiv bo'lmagan ikkilik munosabatlarga (chapda) va uning tranzitiv kamayishiga (o'ngda) mos keladigan grafikalar chizilgan.

Tred-G.svgTred-Gprime.svg

Sonli transitiv kamayish yo'naltirilgan asiklik grafik G noyob va qirralaridan iborat G bu ularning so'nggi nuqtalari orasidagi yagona yo'lni tashkil etadi. Xususan, bu har doim a subgraf berilgan grafikaning Shu sababli, tranzitiv kamayish bu holda minimal ekvivalent grafaga to'g'ri keladi.

Ning matematik nazariyasida ikkilik munosabatlar, har qanday munosabat R to'plamda X deb o'ylash mumkin yo'naltirilgan grafik bu to'plamga ega X uning tepasi o'rnatilgan va u kamonga ega xy har bir kishi uchun buyurtma qilingan juftlik bilan bog'liq bo'lgan elementlarning R. Xususan, ushbu usul imkon beradi qisman buyurtma qilingan to'plamlar yoyi joylashgan yo'naltirilgan asiklik grafikalar kabi qayta talqin qilinishi kerak xy har qanday buyurtma munosabati bo'lganda grafikada x < y qisman tartib berilgan elementlarning juftligi orasida. Tranzitiv qisqartirish operatsiyasi shu tarzda tuzilgan yo'naltirilgan siklik grafikka qo'llanganda u hosil bo'ladi qamrab oluvchi munosabat a yordamida tez-tez vizual ifoda beriladigan qisman tartibning Hasse diagrammasi.

Tranzitiv qisqartirish yo'naltirilgan asiklik grafikalar sifatida ifodalanishi mumkin bo'lgan tarmoqlarda ishlatilgan (masalan.) keltirish grafikalari yoki iqtibos tarmoqlari ) tarmoqlar orasidagi tizimli farqlarni ochib berish.[2]

Tsiklli grafikalarda

Tsikllarga ega bo'lgan cheklangan grafikada o'tish davri kamayishi noyob bo'lmasligi mumkin: bitta vertikal to'plamda minimal qirralarning soniga ega va berilgan grafik bilan bir xil erishish imkoniyatiga ega bo'lgan bir nechta grafalar bo'lishi mumkin. Bundan tashqari, ushbu minimal grafikalarning hech biri ushbu grafikning subgrafasi bo'lmasligi mumkin. Shunga qaramay, minimal grafiklarni berilgan grafik bilan bir xil erishish mumkinligi munosabati bilan tavsiflash to'g'ri G.[3] Agar G o'zboshimchalik bilan yo'naltirilgan grafik va H kabi bir xil erishish imkoniyatiga ega qirralarning mumkin bo'lgan minimal soniga ega bo'lgan grafik G, keyin H dan iborat

  • A yo'naltirilgan tsikl har biriga kuchli bog'langan komponent ning G, ushbu komponentdagi tepaliklarni bir-biriga bog'lab qo'ying
  • Bir chekka xy har bir chekka uchun XY ning tranzitiv kamayishi kondensatsiya ning G, qayerda X va Y ning bir-biriga chambarchas bog'liq ikkita komponenti G kondensatdagi chekka bilan bog'langan, x komponentdagi har qanday tepalik Xva y komponentdagi har qanday tepalik Y. Kondensatsiyasi G ning har bir kuchli bog'langan komponenti uchun tepalikka ega bo'lgan yo'naltirilgan asiklik grafik G va chekka bilan bog'langan har ikki komponent uchun chekka G. Xususan, u asiklik bo'lgani uchun, uning o'tish davri kamayishi oldingi qismda bo'lgani kabi aniqlanishi mumkin.

Ushbu turdagi transitiv reduksiyadagi qirralarning umumiy soni keyinchalik kondensatsiyaning tranzitiv kamayishidagi qirralarning soniga, shuningdek, noan'anaviy ravishda kuchli bog'langan tarkibiy qismlardagi vertikallar soniga (bir nechta vertexga ega komponentlar) teng bo'ladi.

Kondensatsiyalanadigan qirralarga mos keladigan o'tish davri kamayishining qirralari har doim berilgan grafika subgrafasi sifatida tanlanishi mumkin G. Biroq, har bir kuchli bog'langan komponent tarkibidagi tsikl faqat subgrafasi sifatida tanlanishi mumkin G agar bu komponent a ga ega bo'lsa Gamilton tsikli, har doim ham to'g'ri kelmaydigan va tekshirish qiyin bo'lgan narsa. Ushbu qiyinchilik tufayli, shunday Qattiq-qattiq berilgan grafikaning eng kichik subgrafasini topish G bir xil erishish imkoniyati bilan (uning minimal ekvivalenti grafigi).[3]

Hisoblashning murakkabligi

Aho va boshq. ko'rsatish,[3] qachon vaqtning murakkabligi grafik algoritmlari faqat sonning funktsiyasi sifatida o'lchanadi n qirralarning soniga bog'liq emas, balki grafadagi tepaliklarning yo'naltirilgan asiklik grafiklarning tranzitiv yopilishi va transitiv kamayishi bir xil murakkablikka ega. O'tish davri yopilishi va allaqachon ko'rsatilgan edi ko'paytirish ning Mantiqiy matritsalar hajmi n × n bir-biriga o'xshash murakkablikka ega edi,[4] shuning uchun bu natija tranzitiv kamayishni bir xil sinfga kiritdi. Matritsalarni ko'paytirish uchun eng tez ma'lum bo'lgan aniq algoritmlar, 2015 yilga kelib, O vaqtini oladi (n2.3729),[5] va bu zich grafiklarda tranzitiv kamayish uchun eng tez ma'lum bo'lgan eng yomon vaqtni beradi.

Yopish yordamida kamayishni hisoblash

O'tish davri qisqarishi tranzitiv yopilish kabi oson ekanligini isbotlash uchun Aho va boshq. mantiqiy matritsani ko'paytirish bilan allaqachon ma'lum bo'lgan ekvivalentlikka ishonish. Ular ruxsat berishdi A bo'lishi qo'shni matritsa berilgan yo'naltirilgan asiklik grafikning va B uning o'tish davri yopilishining qo'shni matritsasi bo'ling (har qanday standart tranzitiv yopish algoritmi yordamida hisoblab chiqing). Keyin chekka uv ketma-ket nolga teng yozuv bo'lsa, o'tish davri kamayishiga tegishli siz va ustun v matritsaning A, va matritsa mahsulotining bir xil holatida nol yozuv mavjud AB. Ushbu qurilishda matritsaning nolga teng bo'lmagan elementlari AB ikki yoki undan ortiq uzunlikdagi yo'llar bilan bog'langan tepalik juftliklarini ifodalaydi.[3]

Kamaytirish yordamida yopilishni hisoblash

O'tish davri qisqarishi tranzitiv yopilish kabi qiyinligini isbotlash uchun Aho va boshq. berilgan yo'naltirilgan asiklik grafikdan tuzing G boshqa grafik H, unda har bir tepalik G o'rniga uchta vertikal yo'l va har bir chekka bilan almashtiriladi G ning chekkasiga to'g'ri keladi H ushbu yo'llarning mos keladigan o'rta tepaliklarini bog'lash. Bundan tashqari, grafikda H, Aho va boshq. har bir yo'lning boshidan har bir yo'lning oxiriga chekka qo'shing. Ning o'tish davri qisqarishida H, yo'lni boshlash uchun chekka bor siz yo'lning oxirigacha v, agar va faqat chekka bo'lsa uv ning o'tish davri yopilishiga tegishli emas G. Shuning uchun, ning H samaradorligini hisoblash mumkin, o'tish davri yopilishi G to'g'ridan-to'g'ri undan o'qish mumkin.[3]

Siyrak grafikalar kamayishini hisoblash

Ikkala raqam bo'yicha o'lchanganida n tepaliklar va son m yo'naltirilgan asiklik grafadagi qirralarning, o'tish vaqtining kamayishini O vaqtida ham topish mumkin (nm), matritsani ko'paytirish usullaridan tezroq bo'lishi mumkin bo'lgan chegara siyrak grafikalar. Buning uchun a chiziqli vaqt eng uzun yo'l algoritmi berilgan vertikal grafada har bir boshlang'ich vertikani tanlash uchun. Hisoblangan eng uzun yo'llardan faqat bitta uzunlikdagi yo'llarni saqlang (bitta chekka); boshqacha qilib aytganda, bu chekkalarni saqlang (siz,v) uchun boshqa yo'l yo'q siz ga v. Ushbu O (nm) vaqt chegarasi yordamida o'tish davri yopilishlarini qurish murakkabligiga mos keladi chuqurlik birinchi izlash yoki birinchi izlashning kengligi har bir boshli tepalikni tanlash mumkin bo'lgan tepaliklarni topish uchun, shuning uchun yana bu taxminlar bilan tranzitiv yopilishlar va transitiv kamayishlarni bir xil vaqt ichida topish mumkin.

Izohlar

  1. ^ Moyl va Tompson (1969).
  2. ^ Clough va boshq. (2015).
  3. ^ a b v d e Aho, Garey va Ullman (1972)
  4. ^ Aho va boshq. bu natijani Yan Munroning nashr qilinmagan 1971 yildagi qo'lyozmasi va 1970 yilda M. E. Furman tomonidan rus tilida chop etilgan maqolasiga ishontiring.
  5. ^ Le Gall (2014).

Adabiyotlar

  • Aho, A. V.; Garey, M. R.; Ullman, J. D. (1972), "Yo'naltirilgan grafikning o'tish davri kamayishi", Hisoblash bo'yicha SIAM jurnali, 1 (2): 131–137, doi:10.1137/0201008, JANOB  0306032.
  • Klou, J. R .; Gollings, J .; Loach, T. V.; Evans, T. S. (2015), "Iqtibos tarmoqlarini tranzitiv qisqartirish", Kompleks tarmoqlar jurnali, 3 (2): 189–203, arXiv:1310.8224, doi:10.1093 / comnet / cnu039.
  • Moylz, Dennis M.; Tompson, Jerald L. (1969), "Digrafning minimal ekvivalent grafigini topish algoritmi", ACM jurnali, 16 (3): 455–460, doi:10.1145/321526.321534.
  • Le Gall, Fransua (2014), "Tensorlarning kuchlari va tezkor matritsani ko'paytirish", Proc. Simvolik va algebraik hisoblash bo'yicha 39-xalqaro simpozium (ISSAC '14), 296-303 betlar, doi:10.1145/2608628.2608664.

Tashqi havolalar