WikiDer > Trapetsiya grafigi

Trapezoid graph

Yilda grafik nazariyasi, trapezoid grafikalar bor kesishish grafikalari ning trapezoidlar ikkita gorizontal chiziq o'rtasida. Ular o'zaro taqqoslanadigan grafikalar sinfini o'z ichiga oladi intervalli grafikalar va almashtirish grafikalari subklasslar sifatida. Grafik a trapetsiya grafigi agar grafaning tepalariga to'g'ri keladigan trapezoidlar to'plami mavjud bo'lsa, shunday qilib ikkita tepalik chekka bilan birlashtiriladi va agar mos keladigan trapezoidlar kesishgan bo'lsa. Trapezoidal grafikalar tomonidan kiritilgan Dagan, Golumbicva Pinter 1988 yilda. U erda mavjud ${ displaystyle {O} (n log n)}$ tortilgan xromatik son uchun algoritmlar mustaqil to'plam, klik qopqoq va maksimal tortilgan klik.

1-rasm: G grafikasining trapezoidal tasviri.

Ta'riflar va tavsiflar

Kanal, ikkita gorizontal chiziq juftligi berilgan bo'lsa, ushbu chiziqlar orasidagi trapetsiya yuqoridagi ikkita nuqta va pastki chiziqdagi ikkita nuqta bilan belgilanadi. Agar grafaning tepalariga to'g'ri keladigan trapezoidlar to'plami mavjud bo'lsa, unda ikkita tepalik chekka bilan birlashtirilsa, faqatgina tegishli trapezoidlar kesishgan taqdirda, bu trapezoid grafidir. Qisman tartiblangan to'plamning intervalli tartib o'lchovi, ${ displaystyle P = (X, <)}$ , P oraliq buyurtmalarining minimal d soni₁ … P_d shunday qilib P = P₁∩… ∩P_d. Qisman tartiblangan to'plamning taqqoslanmaslik grafigi ${ displaystyle P = (X, <)}$ yo'naltirilmagan grafik ${ displaystyle G = (X, E)}$ qayerda x ga qo'shni y agar Gda va faqat agar x va y Pda taqqoslab bo'lmaydigan narsa, yo'naltirilmagan grafik trapezoidal grafitdir, agar u faqat oraliq tartib o'lchamiga ega bo'lgan qisman tartibning tengsizligi grafigi bo'lsa.^[1]

Ilovalar

Maksimal kliklarni topish va trapetsiya grafikalarini bo'yash muammolari kanallarni yo'naltirish muammolariga bog'liq VLSI dizayn. Ikki tomonlama kanalning yuqori va pastki qismidagi ba'zi etiketli terminallarni hisobga olgan holda, xuddi shu yorliqli terminallar umumiy tarmoqqa ulanadi. Ushbu tarmoq bir xil yorliqli eng o'ng terminallari va eng chap terminallarini o'z ichiga olgan trapezoid bilan ifodalanishi mumkin. Tarmoqlar kesishmasiz yo'naltirilishi mumkin, agar ular mos keladigan trapezoidlar kesishmasa. Shuning uchun to'rlarni kesishmasdan yo'naltirish uchun zarur bo'lgan qatlamlar soni grafaning xromatik soniga teng.

Ekvivalent vakolatxonalar

Trapezoidal tasvir

Trapezoidlar trapezoid grafigi ta'rifidan foydalanib trapezoid grafigini aks ettirish uchun ishlatilishi mumkin. Trapezoid grafasining trapezoid tasvirini 1-rasmda ko'rish mumkin.

Sandiqni namoyish qilish

Hukmron to'rtburchaklar yoki quti tasviri trapezoidal tasvirning ikkita chizig'ining pastki qismidagi nuqtalarni x-aksis va yuqori chiziqning yotishi kabi y-evklid tekisligining ekssisi. Keyin har bir trapezoid tekislikdagi o'qi-parallel qutiga to'g'ri keladi. Hukmronlik tartibi tushunchasidan foydalanish (In R^K, x tomonidan ustunlik qilinganligi aytiladi y, belgilangan x < y, agar x_men dan kam y_men uchun men = 1, …, k), biz bir quti b quti ustunlik qiladi deymiz b ' ning pastki burchagi bo'lsa b ning yuqori burchagida ustunlik qiladi b '. Bundan tashqari, agar ikkita qutining biri boshqasida ustunlik qilsa, biz ularni taqqoslash mumkin deb aytamiz. Aks holda, ularni taqqoslab bo'lmaydi. Shunday qilib, ikkita trapezoid, agar ularning mos keladigan qutilari taqqoslanadigan bo'lsa, ayiriladi. Qutini namoyish qilish foydalidir, chunki tegishli ustunlik tartibi supurish chizig'i algoritmlaridan foydalanishga imkon beradi.^[2]

Bitolerans grafikalari

Bitolerans grafikalari - bitolerans tartibining taqqoslanmaydigan grafikalari. Buyurtma, agar intervallar I bo'lsa, faqat biterans buyurtmasi_x va haqiqiy sonlar t₁(x) va t_r(x) har bir tepaga tayinlangan x shunday qilib x < y agar va faqatgina I ning ustma-ust tushishi bo'lsa_x va men_y ikkalasidan ham kam t_r(x) va t₁(y) va I markazi_x I ning markazidan kamroq_y.^[3] 1993 yilda Langley chegaralangan bitolerans grafikalari trapezoid grafikalar sinfiga teng ekanligini ko'rsatdi.^[4]

Graflarning boshqa oilalari bilan aloqasi

Trapezoid grafikalar sinfi intervalli va permutatsion grafiklarning birlashuvini to'g'ri o'z ichiga oladi va intervalli tartib o'lchoviga ega bo'lgan qisman tartiblangan to'plamlarning taqqoslanmaydigan grafikalariga tengdir. Permutatsion grafikalar har bir trapetsiya nol maydonga ega bo'lganda, trapetsiya grafikalarining maxsus holati sifatida qaralishi mumkin. Bu trapezoidning yuqori kanalidagi ikkala nuqtasi bir xil holatda va pastki kanalning ikkala nuqtasi bir xil holatda bo'lganda sodir bo'ladi.

Barcha taqqoslanmaydigan grafikalar singari, trapetsiya grafikalari ham shundaydir mukammal.

Dairesel trapezoid grafikalar

Dairesel trapezoid grafikalar - Felsner va boshqalar tomonidan taklif qilingan grafikalar klassi. 1993 yilda. Ular trapezoidlar graflari sinfining superklassi, shuningdek, doiraviy va dairesel graflik grafikalarini o'z ichiga oladi. Doira trapezoidasi - bu o'zaro bog'liq bo'lmagan ikkita akkord o'rtasida joylashgan doiradagi mintaqa va aylana trapezoid grafasi - bu umumiy doiradagi doira trapezoidlari oilalarining kesishish grafigi. Bor ${ displaystyle O (n ^ {2})}$ maksimal vaznli mustaqil to'plam uchun algoritm va ${ displaystyle {O} (n ^ {2} log n)}$ maksimal tortilgan klik muammosi algoritmi.

k-Trapezoid grafikalar

k-Trapezoid grafikalar - bu trapetsiya grafikalarining kattaroq kattalik tartiblariga kengaytmasi. Ular birinchi marta Felsner tomonidan taklif qilingan va ular ustun bo'lgan qutilarning ta'rifiga tayanib, o'lchamlari yuqoriroq bo'lgan o'lchamlar x vektor bilan ifodalanadi ${ displaystyle (x_ {1}, ldots, x_ {k})}$ . Yordamida (k - 1) koordinatalarni saqlash va so'rash uchun o'lchovli oraliq daraxtlari, Felsnerning xromatik son algoritmlari, maksimal klik va maksimal mustaqil to'plam uchun qo'llanilishi mumkin. k-trapezoid grafikalar ${ displaystyle {O} (n log ^ {k-1} n)}$ vaqt.

Algoritmlar

Trapetsiya grafikalari algoritmlarini umumiy taqqoslash grafikalari algoritmlari bilan taqqoslash kerak. Ushbu kattaroq grafikalar klassi uchun maksimal mustaqil to'plam va minimal klik qopqoq muammosi echilishi mumkin ${ displaystyle {O} (n ^ {2} log n)}$ vaqt.^[5]Dagan va boshq. birinchi taklif qilingan ${ displaystyle {O} (nk)}$ trapezoid grafikalarini bo'yash algoritmi, bu erda n - tugunlar soni va k - grafikning xromatik soni. Keyinchalik, trapezoid grafalarining quti tasviridan foydalanib, Felsner nashr etdi ${ displaystyle {O} (n log n)}$ xromatik son, algoritmlangan mustaqil to'plam, klik qopqog'i va maksimal tortilgan klik algoritmlari. Ushbu algoritmlarning barchasi talab qiladi ${ displaystyle {O} (n)}$ bo'sh joy. Ushbu algoritmlar chiziqli algoritmlardan foydalanishga imkon beradigan qutidagi tasvirdagi tegishli ustunlikka tayanadi. Felsner muvozanatli daraxtlardan foydalanishni taklif qiladi, ular qo'shish, o'chirish va so'rovlarni bajarishi mumkin ${ displaystyle {O} ( log n)}$ natijada paydo bo'ladigan vaqt ${ displaystyle {O} (n log n)}$ algoritmlar.

E'tirof etish

Grafik yoki yo'qligini aniqlash uchun ${ displaystyle {G}}$ trapezoid grafigi, tranzitiv yo'nalishni qidirish ${ displaystyle {F}}$ ning to‘ldiruvchisida ${ displaystyle {G}}$ . Trapetsiyali grafikalar birgalikda taqqoslanadigan grafikalar to'plami bo'lganligi sababli, agar ${ displaystyle {G}}$ trapezoid grafigi, uni to'ldiruvchi ${ displaystyle {G '}}$ taqqoslanadigan grafik bo'lishi kerak. Agar tranzitiv yo'nalish bo'lsa ${ displaystyle {F}}$ to‘ldiruvchining ${ displaystyle {G '}}$ mavjud emas, ${ displaystyle {G}}$ trapetsiya grafigi emas. Agar ${ displaystyle {F}}$ mavjudmi, tomonidan berilgan tartibni tekshirib ko'ring ${ displaystyle {F}}$ trapetsiya tartibidir. Trapetsiya tartibini tanib olishning eng tezkor algoritmi Makkonnell va Spinrad tomonidan 1994 yilda taklif qilingan, uning ishlash vaqti ${ displaystyle O (n ^ {2})}$ . Jarayon intervalli o'lchov 2-savolni bog'liq ikki tomonlama grafikni zanjirli grafikalar bilan qoplash muammosigacha kamaytiradi (induksiyalangan 2K bo'lmagan grafikalar)₂).^[6]To'g'ri bo'linishni ishlatib, trapetsiya grafikalarini tanib olish muammosi Mertzios va Korneil tomonidan muvaffaqiyat qozonish uchun ko'rsatildi. ${ displaystyle O (n (n + m))}$ vaqt, qayerda ${ displaystyle m}$ qirralarning sonini bildiradi. Ushbu jarayon ma'lum bir grafikani oshirishni o'z ichiga oladi ${ displaystyle {G}}$ , so'ngra kengaytirilgan grafani asl grafaning har bir tepasini bir juft yangi tepalikka almashtirish bilan o'zgartiring. Ushbu "bo'linish grafigi" maxsus xususiyatlarga ega bo'lgan permutatsiya grafigi, agar u bo'lsa ${ displaystyle {G}}$ trapezoid grafigi.^[7]

Izohlar

^ Ido Dagan, Martin Charlz Golumbich va Ron Yair Pinter. Trapetsiya grafikalari va ularning ranglanishi. Alohida dastur. Matematik., 35-46, 1988 yil.
^ Stefan Felsner, Rudolf Myuller va Lorenz Vernish. Trapezoid grafikalar va umumlashmalar, geometriya va algoritmlar. Algoritm nazariyasida - SWAT '94 (Orhus, 1994), Kompyuterdagi ma'ruza yozuvlarining 824 jildi. Ilmiy ishlar, 143–154 betlar. Springer, Berlin, 1994 yil.
^ Kennet P. Bogart, Gart Isaak. To'g'ri va birlik bitolerans buyurtmalari va grafikalari. Diskret matematika 181 (1-3): 37-51 (1998).
^ Martin Charlz Golumbich va Irit B.-A. Xartman, tahrir., Grafika nazariyasi, kombinatorika va algoritmlar: fanlararo qo'llanmalar, Springer-Verlag, Nyu-York, 2005
^ R. Makkonnel va J. Spinrad, chiziqli vaqtli modulli parchalanish va yo'naltirilmagan grafikalarning samarali tranzitiv yo'nalishi, Proc. 5. Ann. Simp. Discr. Alg. (1994).
^ Golumbich, Martin Charlzva Ann N. Trenk. Bag'rikenglik grafikalari. Kembrij [u.a .: Kembrij universiteti, 2004 y.
^ G. B. Mertzios va D. G. Kornil. Vertexning bo'linishi va trapetsiya grafikalarini tanib olish. Diskret amaliy matematika, 159 (11), 1131-1147 betlar, 2011 y.

Adabiyotlar

Golumbich, Martin Charlz (1980). Algoritmik grafik nazariyasi va mukammal grafikalar. Akademik matbuot. ISBN 0-444-51530-5.CS1 maint: ref = harv (havola) Ikkinchi nashr, Annals of Discrete Mathematics 57, Elsevier, 2004.

[1] Ido Dagan, Martin Charlz Golumbich va Ron Yair Pinter. Trapetsiya grafikalari va ularning ranglanishi. Alohida dastur. Matematik., 35-46, 1988 yil.

[2] Stefan Felsner, Rudolf Myuller va Lorenz Vernish. Trapezoid grafikalar va umumlashmalar, geometriya va algoritmlar. Algoritm nazariyasida - SWAT '94 (Orhus, 1994), Kompyuterdagi ma'ruza yozuvlarining 824 jildi. Ilmiy ishlar, 143–154 betlar. Springer, Berlin, 1994 yil.

[3] Kennet P. Bogart, Gart Isaak. To'g'ri va birlik bitolerans buyurtmalari va grafikalari. Diskret matematika 181 (1-3): 37-51 (1998).

[4] Martin Charlz Golumbich va Irit B.-A. Xartman, tahrir., Grafika nazariyasi, kombinatorika va algoritmlar: fanlararo qo'llanmalar, Springer-Verlag, Nyu-York, 2005

[5] R. Makkonnel va J. Spinrad, chiziqli vaqtli modulli parchalanish va yo'naltirilmagan grafikalarning samarali tranzitiv yo'nalishi, Proc. 5. Ann. Simp. Discr. Alg. (1994).

[6] Golumbich, Martin Charlzva Ann N. Trenk. Bag'rikenglik grafikalari. Kembrij [u.a .: Kembrij universiteti, 2004 y.

[7] G. B. Mertzios va D. G. Kornil. Vertexning bo'linishi va trapetsiya grafikalarini tanib olish. Diskret amaliy matematika, 159 (11), 1131-1147 betlar, 2011 y.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Navigation