3.Graf 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 ketma- ketligi, 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
|
