Grafika qat'iyligi - Graph toughness
Yilda grafik nazariyasi, qattiqlik ning o'lchovidir ulanish grafik. Grafik G deb aytilgan t- berilgan narsa uchun qattiq haqiqiy raqam t agar, har bir kishi uchun tamsayı k > 1, G bo'linib bo'lmaydi k boshqacha ulangan komponentlar dan kamini olib tashlash orqali tk tepaliklar. Masalan, grafik 1- agar tepaliklar to'plamini olib tashlash natijasida hosil bo'ladigan komponentlar soni har doim ko'pi bilan olib tashlangan tepalar soniga teng bo'lsa. Grafikning qattiqligi maksimal darajada t buning uchun t- qattiq; bu barcha sonli grafikalar uchun cheklangan son to'liq grafikalar, bu odatiy ravishda cheksiz qattiqlikka ega.
Grafika qat'iyligi birinchi marta tomonidan kiritilgan Vatslav Chvatal (1973 ). O'shandan beri boshqa matematiklar tomonidan qattiqlik bo'yicha keng ko'lamli ishlar olib borildi; tomonidan yaqinda o'tkazilgan so'rovnoma Bauer, Broersma va Shmeyxel (2006) ushbu mavzu bo'yicha 99 ta teorema va 162 ta maqolani sanab o'tdi.
Misollar
Olib tashlash k a dan tepaliklar yo'l grafigi qolgan grafani shuncha songa ajratishi mumkin k + 1 ulangan komponentlar. Komponentlarning olib tashlangan tepaliklarga maksimal nisbati bitta tepalikni (yo'lning ichki qismidan) olib tashlash va uni ikkita komponentga bo'lish orqali amalga oshiriladi. Shuning uchun yo'llar 1/2- qattiq. Aksincha, olib tashlash k a dan tepaliklar tsikl grafigi eng ko'p barglar k qolgan ulangan tarkibiy qismlar va ba'zan to'liq qoldiradi k ulangan komponentlar, shuning uchun tsikl bo'ladi 1- qattiq.
Vertikal ulanishga ulanish
Agar grafik t- qattiq, keyin bitta natija (sozlash orqali olingan k = 2) bu har qanday to'plamdir 2t − 1 tugunlarni grafikani ikkiga bo'linmasdan olib tashlash mumkin. Ya'ni, har bir kishi t- qattiq grafik ham 2t- vertex bilan bog'langan.
Hamiltoniklik bilan bog'lanish
 | Matematikada hal qilinmagan muammo: Raqam bormi? shunday har bir -gamiltonlik grafigimi? (matematikada ko'proq hal qilinmagan muammolar) |
Chvatal (1973) har bir narsani kuzatgan tsikl va shuning uchun har biri Gamilton grafikasi, bo'ladi 1- qattiq; ya'ni bo'lish 1- qattiq a zarur shart Grafil Hamiltonian bo'lishi uchun. U qattiqlik va Gamiltoniklik o'rtasidagi bog'liqlik har ikki yo'nalishda ham borligini taxmin qildi: chegara mavjud t shunday har bir t-gamilton grafigi. Chvatalning asl gumoni t = 2 isbotlagan bo'lar edi Fleyshner teoremasi lekin tomonidan rad etildi Bauer, Broersma va Veldman (2000). Hamiltoniklik uchun kattaroq qat'iylik chegarasining mavjudligi ochiq bo'lib qoladi va ba'zan shunday nomlanadi Chvatalning qat'iyatlilik gumoni.
Hisoblashning murakkabligi
Grafik ekanligini tekshirish 1- qattiq hamkorlikdagi NP - to'liq. Ya'ni qaror muammosi uning javobi 1-darajali bo'lmagan grafik uchun "ha" va 1-darajali bo'lgan grafik uchun "yo'q" bo'lsa To'liq emas. Xuddi shu narsa har qanday qat'iy ijobiy uchun ham amal qiladi ratsional raqam q: grafik yoki yo'qligini tekshirish q-tough birgalikda NP bilan to'ldirilgan (Bauer, Hakimi va Shmeyxel 1990 yil ).
Shuningdek qarang
- Grafik kuchliligi, chekka o'chirish uchun o'xshash kontseptsiya
- Tutte-Berge formulasi, grafadagi maksimal mos keladigan o'lchamlarning tegishli tavsifi
Adabiyotlar
- Bauer, Duglas; Broersma, Xajo; Shmeyxel, Edvard (2006), "Grafikdagi qat'iylik - so'rovnoma", Grafika va kombinatorika, 22 (1): 1–35, doi:10.1007 / s00373-006-0649-0, JANOB 2221006, S2CID 3237188.
- Bauer, D .; Broersma, H. J .; Veldman, H. J. (2000), "Har ikkala qattiq grafik ham Hamiltonian emas", Graflar va kombinatorial optimallashtirish bo'yicha Tventdagi 5-seminar ishi (Enshed, 1997), Diskret amaliy matematika (1-3 nashr), 99 (1–3): 317–321, doi:10.1016 / S0166-218X (99) 00141-9, JANOB 1743840.
- Bauer, D .; Hakimi, S. L.; Shmeyxel, E. (1990), "Qattiq grafikalarni tan olish NP-qattiq", Diskret amaliy matematika, 28 (3): 191–195, doi:10.1016 / 0166-218X (90) 90001-S, JANOB 1074858.
- Chvatal, Vatslav (1973), "Qattiq grafikalar va Gamilton sxemalari", Diskret matematika, 5 (3): 215–228, doi:10.1016 / 0012-365X (73) 90138-6, JANOB 0316301.