Mavzu: Graf daraxtini qurish va murakkablik darajasini baholash usullari

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 yoki uning barcha qirralari ildizdan uzoqroqqa qaratadi, bu holda u daraxtzor yoki tashqaridagi daraxt deb ataladi yoki uning barcha qirralarini ildizga qaratib qo'yish - bu holda u daraxtga qarshi yoki daraxt ichidagi deb ataladi. Ildizli daraxtning oʻzi baʼzi mualliflar tomonidan yoʻnaltirilgan grafik sifatida taʼriflangan. 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. 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.
G rafik 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 grafikdir.

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 tartiblangan.

5. Ulangan grafik

Bir tugundan biz boshqa istalgan tugunga tashrif buyurishimiz mumkin bo'lgan grafik bog'langan grafik deb nomlanadi.
6. Uzilgan grafik
T ugundan 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 bo'lgan grafik.

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 grafik deb nomlanadi.

11. Yo‘naltirilgan asiklik grafik
Hech qanday tsiklni o'z ichiga olmaydigan yo'naltirilgan grafik.
12. Ikki tomonlama grafik
H ar bir to'plamdagi cho'qqida ular orasidagi chekka bo'lmasligi uchun cho'qqini ikkita to'plamga bo'lish mumkin bo'lgan grafik.

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 G H I


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
Shenvi va Smit
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'ridan-to'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'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