|
Ma’lumotlar tarmoq tuzilmalari
|
| bet | 4/4 | | Sana | 24.05.2024 | | Hajmi | 207,7 Kb. | | #252334 |
Bog'liq 5.1-mustaqil ishiMa’lumotlar tarmoq tuzilmalari.
Og’irlikka (vaznga) ega bo’lgan graf (weighted graph) – bu qirralari (yo’ylari) og’irliklari bilan berilgan graf hisoblandi. (i,j) qirraning og’irligi wij kabi belgilanadi.
Og’irlikka ega bo’lgan graf
Agar V to`plamning quvvati n gatengbo`lsa, n soni grafning tartibi deyiladi. Agar V to`plamning quvvati n ga teng bo`lsa, E to`plamning quvvati m ga teng bo`lsa, graf (n, m) graf deyiladi.
Tugun 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)
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.
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.
Grafni to'ldiruvchisi bu aynan bir tugunlar va aynan bir qirralardan tashkil topgan va mavjud grafni to'liq bo'lishini ta'minlovchi grafga aytiladi.
to’liq graf
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
To'yingan grafik (zich grafik) - bu qirralarning soni maksimal mumkin bo'lgan raqamga teng bo'lgan grafik hisoblanadi. (D>0,5)
siyrak grafik (siyrak grafik) - chekkalari tugunlarning oxiriga yaqin joylashgan grafik. (D<0,5)
a) to`yingan grafik (D=0,9)
b) siyrak grafik (D=0,33)
Quyida turli ko`rinishdagi grafiklar keltirilgan. nom oddiy grafik , c-to‘liq grafik, e-multigraf, f-psevdograf, g-digrafda zanjir , h-digrafda ommaviy.
Statik struktura matritsasi yoki dinamik tuzilma ro'yxatlari kompyuter dasturlash tillari xotirasida yo'naltirilmagan, yo'naltirilgan va yo'naltirilgan grafiklarni tasvirlash , ya'ni ularni xotirada tartibga solish uchun ishlatilishi mumkin. Har bir usul har qanday masalada o'zining afzalliklari va kamchiliklariga ega. Har bir usul yo'naltirilmagan, yo'naltirilgan va yo'naltirilgan grafiklarni ifodalash uchun o'z qoidalariga asoslanib tuzilgan.
Grafikning qo‘shma matritsasi G bu o‘lchamdagi kvadrat A matritsasi bo‘lib,
grafik uchun:
Aij = 1, agar i va j tugunlari chekka bilan bog‘langan bo‘lsa, orfograf uchun
i va j tugunlari orasida chekka bo‘lmasa, Aij = 0 bo‘ladi : Aij = 1, agar i tugundan j tugungacha yoy bo'lsa Aij = 0, agar vaznli grafik uchun i va j tugunlarida yoy tugallanmagan bo'lsa : Aij = Wij, agar i va j tugunlari chekka (yoy) lsa bilan bog'langan bo'lsa. Aij = ∞ Agar i va j tugunlari chekka (yoy) sifatida mavjud bo'lmasa , Qo'shma matritsa asosiy diagonalga nisbatan nosimmetrik bo'ladi, agar u yo'naltirilmagan grafikni ifodalasa va u orfograflarda assimetrik bo'ladi. Qo'shma matritsaning afzalliklari quyidagilardan iborat:
Oson yoqish va o'chirish;
Tugunlarning qo'shniligini tekshirish.
Qo'shma matritsaning kamchiliklari quyidagilardan iborat:
Foydalanilgan adabiyotlar:
Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. Москва-Санкт-Петербург-Киев. Изд. дом «Вильямс», 2003. 1293 стр.
Levetan Anany. Introduction to the design & analisis of algorithms. 3rd ed. Villanova university. New Jersey. 2012. 693 page.
Род Стивенс. Готовые алгоритмы. М.: ДМК Пресс. Питер 2004. 384 стр.
Стивен Скиены. Алгоритмы. Руководство по разработке. Питер 2011. 715 стр.
|
| |
