|
Graf daraxtini Murakkabligini o’lchash
|
| bet | 2/2 | | Sana | 14.05.2024 | | Hajmi | 486,56 Kb. | | #233625 |
Bog'liq Aliqulov FarruxGraf daraxtini Murakkabligini o’lchash
Grafik daraxtining murakkabligini o'lchash maxsus dastur va tahlil maqsadlariga qarab bir necha usul bilan amalga oshirilishi mumkin. Mumkin usullardan biri grafik/daraxtdagi tugunlar va qirralarning sonini uning murakkabligi o'lchovi sifatida ishlatishdir. Yana bir yondashuv - murakkablik ko'rsatkichlari sifatida daraja ketmaketligi, klasterlash koeffitsienti yoki grafik/daraxtning diametri kabi matematik o'lchovlardan foydalanish. Bundan tashqari, eng katta bog'langan komponentlarning o'lchamini, tugunlar orasidagi eng qisqa yo'l masofasini yoki grafik/daraxt murakkabligini o'lchash uchun ko'rsatkichlar sifatida markazlashtirilgan daraja yoki o'zaro markazlashuv kabi turli xil markazlashtirilganlik ko'rsatkichlarini ko'rib chiqish mumkin. Umuman olganda, chora-tadbirlarni tanlash aniq muammoga va tahlilda talab qilinadigan tafsilotlar darajasiga bog'liq.
Fon:
Matematik fikrni ifodalashning 5 ta usuli mavjud: so‘zlar/matn, raqamlar jadvallari, chizmalar/rasmlar, ramziy ifodalar, sxemalar/grafiklar.
"Grafiklar" (quyida) haqida so'raganimda, men x-vs-y (aka uchastka) munosabatlarining rasmini nazarda tutmayapman, lekin men tugunlar va qirralar, grafik nazariyasi versiyasini nazarda tutyapman. Men shuningdek, grafik ulangan deb taxmin qilaman hech qanday tugun yo'qki, qirralarni kesib o'tish orqali u tugundan grafikdagi boshqa tugunga o'tish mumkin emas.
So'zlar matn ichida dastur uchun siklomatik murakkablik g'oyasi mavjud.
Ramziy ifodalar ichida biz operatorlar soni va parametrlar sonini ko'rib, ifodaning murakkabligi haqida tasavvurga ega bo'lishimiz mumkin.
Ulanish: grafik bog'langanmi - ya'ni siz istalgan boshqa tugundan istalgan tugunga erisha olasizmi yoki grafikni "orollar" yoki bir-biridan erishib bo'lmaydigan hududlarga bo'lishingiz mumkinmi?
Daraxt testi: grafik daraxt shakliga mos keladimi (ya'ni, bitta, noyob yo'l orqali istalgan boshqa tugundan istalgan tugunga erisha olasizmi?)
Ikki tomonlama test: ba'zi grafiklar ikki tomonlama, ya'ni ular ikkita tugun guruhidan iborat bo'lib, har bir guruh a'zolari faqat boshqa guruh a'zolari bilan bog'lanadi. Masalan, binolar va ulangan kommunal xizmatlar (gaz, elektr, suv) grafigi ikki tomonlama bo'ladi.
Planarlik: grafik tekislikmi? Ya'ni, uni 2 o'lchovli yuzada shunday chizish mumkinmiki, bir-birini kesib o'tadigan hech qanday qirralar chizilmasligi kerak?
Gamilton/Eularian testlari - grafikdagi har bir tugunga bir xil chekkadan ikki marta foydalanmasdan erishish mumkinmi? Grafikda har bir chekka bir marta va faqat bir marta tashrif buyuradigan yo'lni kuzatish mumkinmi?
Klik tahlili: grafikning maksimal klik soni qancha va bu raqamgacha har bir o'lchamdagi nechta kliklar mavjud?
Markaz, diametr, ekssentriklik, periferiya, aylana, kengayish va radius o'lchovlari: grafikning turli tomonlarini tavsiflovchi boshqa (to'liq bo'lmagan) ko'rsatkichlar
Xulosa
Grafik daraxtini qurish murakkab tizimni ierarxik tuzilma sifatida ifodalashni o'z ichiga oladi, bu erda har bir komponent tugun va ular orasidagi bog'lanishlar qirralardir. Grafik daraxtini qurishning turli usullari mavjud, jumladan, yuqoridan pastga, pastdan yuqoriga va ierarxik klasterlash. Grafik daraxtidagi murakkablik darajasini uning chuqurligini, daraja taqsimotini va klasterlash koeffitsientini o'lchash orqali baholash mumkin. Bundan tashqari, markazlashtirilganlik va modullik kabi tarmoq choralari grafik daraxtining tuzilishi va murakkabligi haqida tushuncha berishi mumkin. Grafik daraxtini yaratish usullarini tushunish va uning murakkablik darajasini baholash ijtimoiy tarmoqlar, biologik tizimlar va transport tarmoqlari kabi murakkab tizimlarni tahlil qilish uchun muhimdir.
Foydalanilgan adabiyotlar
R. E. Ladner "On the structure of polynomial time reducibility," ACM jurnali 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
Fortnow, Lance (2013). The Golden Ticket: P, NP, and the Search for the
Impossible. Princeton, NJ: Princeton University Press. ISBN 9780691156491.
Kuk, Stiven (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. 151-158 betlar.
L. A. Levin (1973). "Универсальные задачи перебора" (rus tilida). 9 (3) (Problems of Information Transmission ed.): 115–116.
Fortnov, Lans (2009). "The status of the P ga qarshi NP muammo " (PDF). ACM aloqalari.
|
| |
