• Toyingan grafik
  • Foydalanilgan adabiyotlar
  • Ma’lumotlar tarmoq tuzilmalari




    Download 207,7 Kb.
    bet4/4
    Sana24.05.2024
    Hajmi207,7 Kb.
    #252334
    1   2   3   4
    Bog'liq
    5.1-mustaqil ishi

    Ma’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 to`plamning quvvati n ga teng bo`lsa, E to`plamning quvvati 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.

    1. to’liq graf

    2. 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:

    1. Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ. Москва-Санкт-Петербург-Киев. Изд. дом «Вильямс», 2003. 1293 стр.

    2. Levetan Anany. Introduction to the design & analisis of algorithms. 3rd ed. Villanova university. New Jersey. 2012. 693 page.

    3. Род Стивенс. Готовые алгоритмы. М.: ДМК Пресс. Питер 2004. 384 стр.

    4. Стивен Скиены. Алгоритмы. Руководство по разработке. Питер 2011. 715 стр.

    Download 207,7 Kb.
    1   2   3   4




    Download 207,7 Kb.