Muxammad al-Xorazmiy nomidagi Toshkent axborot texnologiyalari Universiteti Urganch filialining kompyuter injinering fakulteti 3-kurs 962-21-gurux (sirtqi) ta’lim talabasi
Ro’ziyev Nuralining Algoritmlarni loyihalash
Fanidan tayyorlagan
Mustaqil ishi
Mavzu ; Graf daraxtini qurish va murakkablik darajasini
baholash usul
Topshirdi: Ro’ziyev Nurali
Qabul qildi: Niyazmetova K.E
Graf daraxtini qurish va murakkablik darajasini
baholash usul
Mundarija:
1) Kirish
2) Asosiy qism: Graf daraxti Graf daraxtini qurish Graf daraxtini Murakkabligini o’lchash Dastur kodi
3) Xulosa
4)Foydalanilgan adabiyotlar
Graf daraxti Grafik nazariyasida daraxt yo'naltirilmagan, bog'langan va asiklik grafikdir. Boshqacha qilib aytganda, hatto bitta siklni ham o'z ichiga olmagan bog'langan grafik daraxt1 deyiladi. Daraxt ierarxik tuzilmani grafik shaklda ifodalaydi. Grafik daraxti algoritmi - bu ildiz deb ataladigan ma'lum bir tugundan boshlab, grafikning barcha uchlari va qirralarini o'rganish uchun ishlatiladigan grafik o'tish algoritmining bir turi. Ushbu algoritmda grafik daraxtga o'xshash struktura sifatida qaraladi, ildiz tugunlari boshlang'ich nuqtadir. Grafiklar nazariyasida daraxt - bu yo'naltirilmagan grafik bo'lib, unda har qanday ikkita cho'qqi aynan bitta yo'l bilan bog'langan yoki ekvivalent ravishda bog'langan asiklik yo'naltirilmagan grafikdir.[1] O'rmon - bu yo'naltirilmagan grafik bo'lib, unda har qanday ikkita cho'qqi ko'pi bilan bitta yo'l bilan bog'langan yoki ekvivalent ravishda asiklik yo'naltirilmagan grafik yoki ekvivalent daraxtlarning ajratilgan birlashuvi bilan bog'langan.[2] Koʻp daraxt[3] (yoki yoʻnaltirilgan daraxt[4] yoki yoʻnaltirilgan daraxt[5][6] yoki yakka bogʻlangan tarmoq[7]) yoʻnaltirilgan asiklik grafik (DAG) boʻlib, uning ostidagi yoʻnaltirilmagan grafigi daraxtdir. Ko'p o'rmon (yoki yo'naltirilgan o'rmon yoki yo'naltirilgan o'rmon) yo'naltirilgan asiklik grafik bo'lib, uning asosiy yo'naltirilmagan grafigi o'rmondir. A labeled tree with 6 vertices and 5 edges. Vertices v Edges v − 1 Chromatic number 2 if v > 1 Informatika fanida daraxtlar deb ataladigan har xil turdagi ma'lumotlar tuzilmalari grafik nazariyasida daraxtlar bo'lgan asosiy grafiklarga ega, garchi bunday ma'lumotlar tuzilmalari odatda ildiz otgan daraxtlardir. Ildizli daraxt yoʻnaltirilgan boʻlishi mumkin, uni yoʻnaltirilgan ildizli daraxt[8][9] yoki uning barcha qirralari ildizdan uzoqroqqa qaratadi, bu holda u daraxtzor[4][10] yoki tashqaridagi daraxt[11] deb ataladi. [12] - yoki uning barcha qirralarini ildizga qaratib qo'yish - bu holda u daraxtga qarshi[13] yoki daraxt ichidagi [11][14] deb ataladi. Ildizli daraxtning oʻzi baʼzi mualliflar tomonidan yoʻnaltirilgan grafik sifatida taʼriflangan.[15][16][17] Ildizli o'rmon - bu ildiz otgan daraxtlarning alohida birlashmasi. Ildizli o'rmon yo'naltirilgan ildizli o'rmon deb nomlanishi mumkin, yoki uning barcha qirralari har bir ildiz otgan daraxtning ildizidan uzoqqa yo'naltirilishi mumkin - bu holda u shoxlangan yoki tashqarida o'rmon deb ataladi - yoki uning barcha qirralari ildizga qaratiladi. har bir ildizli daraxtda - bu holda u shoxlanishga qarshi yoki o'rmon ichidagi deb ataladi. Daraxt atamasi 1857 yilda ingliz matematigi Artur Keyli tomonidan kiritilgan.[18] Algoritm ildiz tuguniga tashrif buyurish va keyin uning barcha qo'shnilarini rekursiv ravishda o'rganish orqali ishlaydi. Ushbu jarayon barcha tugunlarga tashrif buyurilgunga qadar grafikning barcha uchlari uchun takrorlanadi. O'tish jarayonida algoritm allaqachon o'rganilgan tugunni qayta ko'rib chiqmaslik uchun tashrif buyurilgan tugunlar ro'yxatini saqlaydi. Grafik daraxti algoritmi grafikdagi ikkita tugun orasidagi eng qisqa yo'lni topish yoki grafik bog'langan yoki bog'lanmaganligini aniqlash kabi turli muammolarni hal qilish uchun ishlatilishi mumkin. Bundan tashqari, u xususiyatlarni tanlash va klasterlash uchun ma'lumotlarni qidirish va mashinani o'rganish dasturlarida keng qo'llaniladi. Grafik - bu cho'qqilar va qirralardan iborat chiziqli bo'lmagan ma'lumotlar strukturasi. Cho'qqilar ba'zan tugunlar deb ham ataladi va qirralar grafikdagi har qanday ikkita tugunni bog'laydigan chiziqlar yoki yoylardir. Rasmiyroq qilib aytganda, Grafik cho'qqilar to'plami ( V ) va qirralar to'plamidan ( E ) iborat. Grafik G(E, V) bilan belgilanadi
Grafikning komponentlari Vertices: Vertices - bu grafikning asosiy birliklari. Ba'zan, cho'qqilar cho'qqi yoki tugunlar sifatida ham tanilgan. Har bir tugun/cho'qqi etiketli yoki yorliqsiz bo'lishi mumkin. Qirralar: Qirralar chiziladi yoki grafikning ikkita tugunini ulash uchun ishlatiladi. Yo'naltirilgan grafikdagi juft tugunlarni buyurtma qilish mumkin. Qirralar har qanday ikkita tugunni har qanday usulda ulashi mumkin. Hech qanday qoidalar yo'q. Ba'zan qirralarning yoylari sifatida ham tanilgan. Har bir chekka etiketli/yorliqsiz bo'lishi mumkin. Grafiklar ko'plab real hayot muammolarini hal qilish uchun ishlatiladi. Grafiklar tarmoqlarni ifodalash uchun ishlatiladi. Tarmoqlar shahar yoki telefon tarmog'i yoki elektron tarmoqdagi yo'llarni o'z ichiga olishi mumkin. Grafiklar linkedIn, Facebook kabi ijtimoiy tarmoqlarda ham qo'llaniladi. Masalan, Facebook-da har bir shaxs tepa (yoki tugun) bilan ifodalanadi. Har bir tugun tuzilma bo'lib, shaxs identifikatori, ismi, jinsi, mahalliy til va boshqalar kabi ma'lumotlarni o'z ichiga oladi. Grafik turlari 1. Null grafik Grafikda qirralar bo'lmasa, grafik null grafik deb nomlanadi. 2. Trivial grafik Faqat bitta tepaga ega bo'lgan grafik, shuningdek, mumkin bo'lgan eng kichik
3. Yo'naltirilmagan grafik Qirralari hech qanday yo'nalishga ega bo'lmagan grafik. Ya'ni tugunlar har bir chekkaning ta'rifida tartibsiz juftliklardir.
4. Yo'naltirilgan grafik Qirrasi yo'nalishga ega bo'lgan grafik. Ya'ni tugunlar har bir chekkaning ta'rifida juftlik bilan tartiblan
5. Ulangan grafik Bir tugundan biz boshqa istalgan tugunga tashrif buyurishimiz mumkin bo'lgan grafik bog'langan grafik deb nomlanadi.
6. Uzilgan grafik Tugundan kamida bitta tugunga etib bo'lmaydigan grafik ajratilgan grafik deb nomlanadi.
7. Muntazam grafik Har bir cho'qqining darajasi K ga teng bo'lgan grafik K muntazam grafik deb ataladi.
8. To‘liq grafik Har bir tugundan bir-biriga chekka b
9. Tsikl grafigi Grafik o'z-o'zidan tsikl bo'lgan grafik, har bir cho'qqining darajasi 2 ga teng.
10. Tsiklik grafik Kamida bitta tsiklni o'z ichiga olgan grafik siklik
11. Yo‘naltirilgan asiklik grafik Hech qanday tsiklni o'z ichiga olmaydigan yo'naltirilgan grafik.
12. Ikki tomonlama grafik Har bir to'plamdagi cho'qqida ular orasidagi chekka bo'lmasligi uchun cho'qqini ikkita to'plamga bo'lish mumk
13. O'lchovli grafik Qirralari allaqachon mos og'irlik bilan ko'rsatilgan grafik vaznli grafik deb nomlanadi.
Og'irlangan grafiklarni qo'shimcha ravishda yo'naltirilgan vaznli grafiklar va yo'naltirilmagan vaznli grafiklar deb tasniflash mumkin. Daraxt v/s Grafik Daraxtlar cheklangan turdagi grafiklardir, faqat bir nechta qoidalar mavjud.
Har bir daraxt har doim grafik bo'ladi, lekin hamma grafiklar daraxt bo'lmaydi. Bog'langan ro'yxat, daraxtlar va uyalar - bularning barchasi grafiklarning alohida holatlaridir
Grafiklarning tasviri Grafikni saqlashning ikki yo'li mavjud: Qo'shnilik matritsasi Qo'shnilar ro'yxati Qo'shnilik matritsasi Ushbu usulda grafik 2D matritsa shaklida saqlanadi, bu erda satrlar va ustunlar cho'qqilarni bildiradi.
Matritsadagi har bir yozuv ushbu cho'qqilar orasidagi chekka og'irligini ifodalaydi.
Qo'shnilar ro'yxati Ushbu grafik bog'langan ro'yxatlar to'plami sifatida taqdim etilgan.
O'sha cho'qqiga ulangan qirralarga ishora qiluvchi ko'rsatgichlar qatori mavjud
Qo'shnilik matritsasi va qo'shnilik ro'yxati o'rtasidagi taqqoslash Grafikda ko'p sonli qirralar bo'lsa, uni matritsa sifatida saqlash yaxshi, chunki matritsadagi faqat ba'zi yozuvlar bo'sh bo'ladi.
Kamroq murakkablik uchun Prim va Dijkstra qo'shnilik matritsasi kabi algoritm ishlatiladi. Graf daraxtini qurish Grafik daraxtini yaratish uchun siz quyidagi amallarni bajaramiz:
1. Ildiz tugunini tanlang. Ushbu tugun daraxtingizning boshlang'ich nuqtasi bo'ladi.
2. Ildiz tuguniga to'g'ridan-to'g'ri bog'langan bog'langan tugunlar to'plamini tanlang. Bular ildiz tugunining bolalari bo'ladi.
3. Har bir kichik tugun uchun
2-bosqichni takrorlang, lekin ildiz tugunini va uning asosiy tugunlarini ulangan tugunlar to'plamidan chiqarib tashlang.
4. Butun daraxtni qurmaguningizcha har bir tugun uchun
3-bosqichni takrorlang. Grafik daraxtini qurish misoli:
1. Ildiz tugun sifatida A tugunini tanlang. 2. B, C va D tugunlari to'g'ridan-to'g'ri A tuguniga bog'langan. Bular A tugunining bolalari bo'ladi.
3. B tugunlari uchun E va F tugunlari to'g'ridan-to'g'ri bog'langan, ammo A tugunini va C va D tugunlarini to'plamdan chiqarib tashlaydi. C tugunlari uchun G tugunlari to'g'ridan-to'g'ri ulanadi, lekin to'plamdan A, B va D tugunlarini istisno qiladi. D tugunlari uchun H va I tugunlari to'g'ridan-to'g'ri bog'langan, ammo A, B va C tugunlarini to'plamdan chiqarib tashlaydi.
4. Butun daraxtni qurmaguningizcha har bir tugun uchun
3-bosqichni takrorlang. Olingan grafik daraxti quyidagicha ko'rinadi:
``` A
/| \
B C D
/|
/ | \
E F
Men ushbu rasm bilan bog'liq muammomni tasvirlashni boshlayman: bu erda rasm tavsifini kiriting Rasmda biz ba'zi nuqtalarni (qora nuqta) ko'rishimiz mumkin.
Men qilmoqchi bo'lgan narsa birinchi navbatda barcha nuqtalarni saqlash va keyin tugun nuqtalarini va uchi nuqtalarini (qizil nuqta) topishdir. Bundan tashqari, qizil chiziqlar orasidagi burchaklarni topish uchun bu qizil nuqtalarni to'g'ri chiziqlar bilan (qora nuqtalar bo'ylab) bog'lash mumkinligini tekshirishim kerak.
Men buni etarlicha aniq tushuntirdimmi yoki yo'qligini bilmayman, lekin men daraxt/grafikni qo'llashim va qizil nuqtalar ulanganligini tekshirish uchun yo'lni topishim kerak deb o'yladim.
Asosan, men shunday bir narsa bilan boshladim:
class Point
{ public:
int x;
int y;
vector neighbors;
Point(void);
Point(int x, int y);
} vector allPoints;
Barcha nuqtalarni allPoints vektorida saqlaydigan joy.
Har bir nuqta uchun men uning barcha qo'shnilarini tekshiraman ([x+1,y], [x-1,y], [x+1,y+1], [x-1, y+1], ... ) va ularni ushbu nuqta uchun qo'shnilar vektorida saqlang.
Keyin, qo'shnilar vektorining o'lchamiga ko'ra, men Nuqta tugun (3 yoki undan ortiq qo'shni), uchi (1 qo'shni) yoki oddiy bir nuqta (2 qo'shni) ekanligini aniqlayman.
Va bu erda men yo'l topishni qanday amalga oshirishni bilmayman (masalan, uchi nuqtasidan eng yaqin tugun nuqtasiga yo'l bor-yo'qligini tekshirish uchun) qism keladi.
Bundan tashqari, mening "daraxt" tasvirim yaxshi yoki yo'qligini bilmayman (ehtimol bunday emas).
Shunday qilib, agar kimdir menga xohlagan narsaga erishishimga yordam bersa, bu ajoyib bo'lar edi.
P.S. Men C++ (va OpenCV) va VS2010 da yozyapman.
Tahrirlash: Bu haqiqiy dasturda shunday ko'rinadi (qizil chiziqlar men
tomonidan bo'yoqqa botiriladi, lekin men erishmoqchi bo'lgan narsam):
Ko'pgina real jarayonlar nosimmetrik bo'lmagan namunaviy kosmik tuzilmalarni o'z ichiga oladi. Bunday jarayonlarga misollarni ko'pincha sog'liqni saqlash, tibbiyot, xavflarni tahlil qilish va politsiyada topish mumkin (qarang: Collazo va boshqalar. (2018))
Bunday nosimmetrikliklar tizimli nol va tizimli mavjudligi sababli paydo bo'lishi mumkin boshqa o'zgaruvchi(lar)ni amalga oshirish sharti bilan o'zgaruvchining namunaviy fazosida etishmayotgan qiymatlar (birgalikda strukturaviy nosimmetrikliklar).
Strukturaviy nol nolni kuzatishni bildiradi nolga teng bo'lmagan kuzatuvda hisoblash o'zgaruvchisi yoki toifali o'zgaruvchining toifasi uchun chastotalar tanlab olish cheklanishidan ko'ra mantiqiy imkonsizlikdir (masalan, kunlar yoki miqdor past, o'rta, teetotallers tomonidan spirtli ichimliklarni yuqori iste'mol qilish).
Strukturaviy etishmayotgan qiymat - bu kuzatuvlar yo'qolgan, chunki ular shaxslar/birliklarning bir qismi uchun aniqlanmagan (masalan, kasallikka chalingan, ammo operatsiya qilinmagan shaxslarning operatsiyadan keyingi sog'lig'i bilan bog'liq o'zgaruvchilar).
Qanday qilib buni ko'rish oson nosimmetrikliklar kontekstga xos shartli mustaqilliklarni keltirib chiqarishi mumkin, ular mustaqillikdir. X y Y|Z = z1, lekin X 6y Y|Z = z2 ko'rinishdagi munosabatlar, bu erda y ehtimollik mustaqilligini bildiradi va vertikal chiziq o'ng tomonda shartli o'zgaruvchilarni ko'rsatadi.
Aslida, kontekstga xos Mustaqillik muntazam ravishda ko'plab ilovalarda tabiiy ravishda paydo bo'ladi (Chjan va Poole, 1999). Bayes tarmoqlari (BNs) kabi grafik modellar assimetriklikni to'liq tasvirlay olmaydi. jarayonlar. Ular, birinchi navbatda, bu jihatdan to'sqinlik qiladilar, chunki ular jarayon tavsifini a ga majburlaydilar a priori aniqlangan o'zgaruvchilar to'plami. Haqiqatan ham, BN metodologiyalarini kattalashtirish uchun muammolar, yaxshi BN dasturiy ta'minot bitta shartli ehtimollik jadvalining qismlarini nusxalash funktsiyalarini o'z ichiga oladi
1 Shenvi va Smit boshqasiga. Shunday qilib, BNlar o'zlarining shartli ehtimollik jadvallari ichida ehtimolliklarni belgilash orqali kontekstga xos mustaqilliklarni bilvosita o'rnatadilar. Biroq, bu tizimli ma'lumot hech qachon topologiyalarida aniq ifodalangan. Ushbu mustaqilliklarni ochish uchun ularning standart ko'rinishiga va/yoki xulosa chiqarishga jiddiy o'zgartirishlar kiritish (odatda qandaydir shakldagi daraxtlar) talab qilinadi. jarayon (Boutilier va boshq., 1996; Zhang va Poole, 1999; Jabbari va boshq., 2018). Bundan tashqari, strukturaviy nollar ham ularning shartli ehtimollik jadvallarida yashiringan. Chain Voqealar Grafiklari (CEGs) - ehtimollik grafik modellari oilasi, ularning grafiklari vakillik strukturaviy nosimmetrikliklar va kontekstga xos shartli mustaqilliklarni aniq ko'rsatadi (Collazo va boshq., 2018). CEGlar alohida holat sifatida cheklangan diskret BN sinfini o'z ichiga oladi (Smit va Anderson, 2008). Ular voqealar ketma-ketligi orqali jarayonning rivojlanishini tasvirlash uchun tabiiy va intuitiv ramka ishini ta'minlaydigan voqea daraxtlaridan qurilgan. Garchi o'lchami bir hodisalar daraxti jarayonning evolyutsiyasida ishtirok etadigan hodisalar soni bilan chiziqli ravishda ortadi katta murakkab jarayonlar uchun noqulay bo'lishi mumkin, ammo ular statistik uchun osondir domen ekspertining tabiiy tildagi tavsiflaridan shaffof tarzda chiqaring. Strukturaviy o'rnatish Hodisalar daraxti ichidagi nosimmetrikliklar shunchaki tegishli novdani chizmaslik masalasidir daraxt (Shenvi va boshq., 2018). Biroq, saqlab qolgan holda, hodisa daraxtining yanada ixcham vakilligi uning xossalari va shaffofligi maqsadga muvofiqdir. CEG bunday ixcham vakillikni ta'minlaydi. Shuning uchun Bu, ayniqsa tibbiyot (Barclay va boshq., 2013), sog'liqni saqlash (Shenvi va boshq., 2018), sud-tibbiyot kabi asosiy sohalarda sezilarli nosimmetrikliklar ko'rsatadigan jarayonlar uchun kuchli modellashtirish vositasidir. (Collazo va boshq., 2018), bu erda mutaxassislar ko'pincha jarayonlarning voqealarga asoslangan tavsiflarini taklif qilishadi. CEGni olish uchun voqea daraxti birinchi navbatda uchlarini bo'yash orqali bosqichli daraxtga aylantiriladi uning tuzilishidagi simmetriyalarni ifodalaydi. Keyinchalik ta'minlash uchun bosqichli daraxtning uchlari birlashtiriladi CEG grafigi ko'rinishida ushbu simmetriyalarning yanada ixcham tasviri. Bunday transformatsiya natijasida ko'pincha kichikroq cho'qqilar va qirralarning tartibiga ega bo'lgan ancha sodda grafik paydo bo'ladi. hosil qiluvchi daraxtga qaraganda. Hodisalar daraxti singari, CEG ham jarayonni ketma-ketlikda tasvirlaydi hodisalar va shu tariqa strukturaviy nosimmetrikliklarni grafik tasvirlash qobiliyatini meros qilib oladi. CEG taqdimoti ayniqsa foydalidir, chunki turli xil yashirin shartli mustaqilliklar, shu jumladan daraxtning rang berish naqshlari ichida yashiringan kontekstga xos tabiatni to'g'ridanto'g'ri o'qish mumkin uning topologiyasi kesmalar va nozik kesmalar deb ataladigan hodisalar to'plamidan foydalangan holda (Smit va Anderson, 2008). Endi CEG uchun bir nechta tez o'rganish algoritmlari mavjud (Friman va Smit, 2011; Silander va Leong, 2013 yil; Kouell va Smit, 2014). Ushbu algoritmlarning chiqishi bosqichli daraxtdir. Sahnalashtirilgan daraxt odatda ni ifodalashdan oldin ahamiyatsiz bo'lmagan o'zgarishlar ketma- ketligidan o'tishi kerak CEG grafigi. Aslida, CEG o'zining bosqichli daraxti bilan o'ziga xos tarzda aniqlanadi va biz sahnalashtirilganligini ko'rsatamiz daraxt bo'lishi mumkin 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'li
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
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
|
