|
O’zbekiston respublikasi oliy va o’rta maxsus ta’lim vazirligi toshkent axborot texnologiyalari universiteti
|
| bet | 55/163 | | Sana | 16.01.2024 | | Hajmi | 18,84 Mb. | | #138868 |
Bog'liq O zbekiston respublikasi oliy va o rta maxsus ta lim vazirligi tTugun darajasi (vertex degree) – bu undan chiquvchi yoylar soni xisoblanadi. deg(7) = 2, deg(1) = 3
Halqa (cycle) – bu boshi va oxiri tutashuvchi tugundan iborat yo'l hisoblanadi: (4, 6, 7, 8, 3, 4) (1.2.8.-rasm).
G(V, E) grafda uning barcha tugunlari darajalari yig'indisi – juft, grafning qirralari sonining ikkilanganiga teng.
Tugunlar darajasiga nisbatan juft yoki toq deyiladi, agar ularning darajalari mos ravishda juft yoki toq qiymatga teng bo'lsa.
8.-rasm. Grafning halqa va tugun darajasiga misol
To'liq graf (complete graph) – bu istalgan tugunlari qo'shni bo'lgan graf xisoblanadi yani barcha tugunlar o'zaro birlashtirilgan. (9. a -rasm)
Grafni to'ldiruvchisi bu aynan bir tugunlar va aynan bir qirralardan tashkil topgan va mavjud grafni to'liq bo'lishini ta'minlovchi grafga aytiladi. (9. b -rasm)
a)
b)
9.-rasm.a) to’liq graf b) graf va uning to’ldiruvchisi
To'liq, yo'naltirilmagan grafda qirralar soni quyidagi formula (1) orqali aniqlanadi:
(1)
qaerda n – yoylar(tugunlar) soni.
D grafning to'yinganligi (density) grafning qirralrining tugunlar nisbatiga to’liqlik munosabat koefitsientini belgilaydi va quyidagi formula (2) orqali aniqlanadi:
(2)
qaerda n – grafning tugunlar soni, m – grafning qirralar soni.
Grafning to'yinganligi koefitsientiga qarab ikki hil graf ko’rinishi aniqlash mumkin: to'yingan graf va siyrak graf (10.-rasm).
To'yingan graf (dense graph) – bu qirralar soni bo'lishi mumkin bo'lgan maksimalga teng bo'lgan graf xisoblanadi. (D>0.5)
Siyrak graf (sparse graph) – bu qirralari soni tugunlar soniga yaqin bo'lgan grafdir. (D<0.5)
a) b)
10-rasm.a) to'yingan graf (D=0.9) b) siyrak graf (D=0.33)
Quyida turli ko’rinishdagi graflar keltirilgan.
11-rasm. a-d oddiy graf, c-to’liq graf, e-multigraf, f-psevdograf, g-digrafdagi zanjir, h-digrafda xalqa.
|
| |
