WikiDer > Bo'g'ilgan grafik

Bo'g'ilgan grafik, yordamida hosil qilingan klik-summalar yopishtirmoq maksimal planar grafik (sariq) va ikkitasi akkord grafikalari (qizil va ko'k). Qizil akkord grafigi o'z navbatida to'rtta maksimal planar grafikaning (ikki qirrasi va ikkita uchburchagi) klik-yig'indisiga ajralishi mumkin.

Yilda grafik nazariy matematikasi, a bo'g'ilgan grafik har qanday qirralarning yo'q qilinadigan grafigi induktsiya qilingan tsikl uzunligi uchdan katta bo'lar edi uzmoq qolgan grafik. Ya'ni, ular har birining grafikalari periferik tsikl uchburchak

Misollar

A maksimal planar grafikyoki umuman olganda har birida ko'p qirrali grafik, periferik tsikllar grafani planar joylashtirilgan yuzlardir, shuning uchun ko'p yuzli grafik, agar barcha yuzlar uchburchak bo'lsa yoki unga teng ravishda u maksimal tekis bo'lsa, bo'g'iladi. Har bir akkord grafigi bo'g'ilib o'ldirilgan, chunki akkord grafikalaridagi induktsiya qilingan tsikllar faqat uchburchaklardir, shuning uchun o'chiriladigan tsikllar yo'q.

Xarakteristikasi

A klik-sum Ikkita grafikaning ikkitasi bir xil o'lchamdagi o'lchamlarni aniqlash orqali hosil bo'ladi kliklar har bir grafada, so'ngra ba'zi qirralarning qirralarini yo'q qilish. Bo'g'ilgan grafikalar uchun mos keladigan klik-yig'indilar versiyasi uchun chekkani o'chirish bosqichi o'tkazib yuborilgan. Ikkala bo'g'ilgan grafik orasidagi ushbu turdagi klik-yig'indisi boshqa bo'g'ilgan grafikani keltirib chiqaradi, chunki yig'indagi har bir uzoq induktsiya qilingan tsikl u yoki bu tomon bilan chegaralanishi kerak (aks holda u bir tomondan kesib o'tgan tepaliklar o'rtasida akkordga ega bo'lar edi) yig'indining yon tomoni boshqasiga), va tsiklni o'chirish natijasida hosil bo'lgan ushbu tomonning uzilgan qismlari klik-sumda uzilib qolishi kerak. Har qanday akkord grafigi shu tarzda klik-yig'indiga ajralishi mumkin to'liq grafikalar, va har bir maksimal tekislik grafigi klik-yig'indiga ajralishi mumkin 4-vertex bilan bog'langan maksimal planar grafikalar.

Sifatida Seymur va Uayver (1984) Ko'rgazma, bu bo'g'ib qo'yilgan grafikalarning mumkin bo'lgan yagona qurilish bloklari: bo'g'ilgan grafikalar to'liq grafikalar va maksimal planar grafikalarning klik-yig'indisi sifatida shakllanishi mumkin bo'lgan grafikalardir.

Shuningdek qarang

• To'g'ri chiziqli grafik, har bir g'alati tsikl uchburchak bo'lgan grafik

Adabiyotlar

• Seymur, P. D.; Weaver, R. W. (1984), "Akkord grafikalarini umumlashtirish", Grafika nazariyasi jurnali, 8 (2): 241–251, doi:10.1002 / jgt.3190080206, JANOB 0742878.