Mustaqil ish-1 Mavzu: Graf daraxtini qurish va murakkablik darajasini baholash usullari Guruh

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

---

Dasturi
Grafik daraxtini yaratishda ushbu sinfdan foydalanish uchun siz GraphTree sinfining
yangi namunasini yaratishingiz, add_node() usuli yordamida tugunlarni yaratishingiz va
add_node() ga birinchi argument sifatida ota-tugunni o'tkazish orqali ularni bir-biriga
bog'lashingiz mumkin.
Yuqoridagi kod yordamida oddiy grafik daraxtini qanday yaratishingiz mumkinligiga
misol:

---

Ushbu misolda biz 0 qiymatiga ega ildiz tugunli daraxt va mos ravishda 1 va 2 qiymatli
ikkita tugunli tugunni yaratdik. 2-tugunda 3 va 4 qiymatlari bo'lgan ikkita tugun mavjud.
Kattaroq daraxt tuzilishini yaratish uchun shu tarzda daraxtga tugunlarni qo'shishni
davom ettirishingiz mumkin.
Python-da igraph kutubxonasi yordamida daraxt grafigini yaratish misoli:
Ushbu kod 25 ta burchakli daraxt yaratadi va har bir tepada 2 ta bola bor. Daraxt
grafigini qurishning murakkabligi ishlatiladigan maxsus algoritmga va kiritilgan
ma'lumotlarning hajmiga bog'liq. Bunday holda, daraxtni qurishning murakkabligi O (n),
bu erda n - uchlari soni.
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
1. R. E. Ladner "On the structure of polynomial time reducibility," ACM jurnali 22,
pp. 151–171, 1975. Corollary 1.1. ACM site.
2. Fortnow, Lance (2013). The Golden Ticket: P, NP, and the Search for the
Impossible. Princeton, NJ: Princeton University Press. ISBN 9780691156491.
3. Kuk, Stiven (1971). "The complexity of theorem proving procedures". Proceedings
of the Third Annual ACM Symposium on Theory of Computing. 151-158 betlar.
4. L. A. Levin (1973). "Универсальные задачи перебора" (rus tilida). 9 (3)
(Problems of Information Transmission ed.): 115–116.
5. Fortnov, Lans (2009). "The status of the P ga qarshi NP muammo " (PDF). ACM
aloqalari. 52 (9): 78–
86. CiteSeerX 10.1.1.156.767. doi:10.1145/1562164.1562186. Arxivlandi asl
nusxasi (PDF) 2011 yil 24 fevralda. Olingan 26 yanvar 2010.
6. NSA (2012). "Letters from John Nash" (PDF).
7. Hartmanis, Juris. "Gödel, von Neumann, and the P = NP muammo
" (PDF). Nazariy kompyuter fanlari bo'yicha Evropa assotsiatsiyasining
Axborotnomasi. 38: 101–107.
8. Sipser, Michael: Introduction to the Theory of Computation, Second Edition,
International Edition, page 270. Thomson Course Technology, 2006. Definition
7.19 and Theorem 7.20.
9. William I. Gasarch (Iyun 2002). " P=?NP poll" (PDF). SIGACT
yangiliklari. 33 (2): 34–
47. CiteSeerX 10.1.1.172.1005. doi:10.1145/564585.564599.

---

10.William I. Gasarch. "The Second P=?NP poll" (PDF). SIGACT yangiliklari. 74.