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