• 5-jadval. Qirralar roʻyxati 6-jadval. Uchlar roʻyxati
  • -rasm. Yoʻnaltirilmagan grafda insidentlik matritsasi




    Download 4,61 Mb.
    Pdf ko'rish
    bet61/111
    Sana18.05.2024
    Hajmi4,61 Mb.
    #241929
    1   ...   57   58   59   60   61   62   63   64   ...   111
    Bog'liq
    ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARI

    25-rasm. Yoʻnaltirilmagan grafda insidentlik matritsasi 
    26-rasm. Orgrafda insidentlik matritsasi 
     


    91 
    Qoʻshnilik roʻyxati. 
    Qoʻshnilik roʻyxati - bu grafni uchlar roʻyxati 
    ("roʻyxatlar roʻyxati") toʻplami sifatida koʻrsatish usuli - grafning har bir 
    uchi qoʻshni uchlar roʻyxatiga toʻgʻri keladi. Masalan, 1-rasmni biz 
    quyidagi qoʻshnilik roʻyxati bilan tavsiflashimiz mumkin: 
    a: {b, c, d, e} 
    b: {a} 
    c: {a, d} 
    d: {a, c, e} 
    e: {a, f} 
    f: {e} 
    Bu sodda graflarni aks ettirish uchun ham, grafni kenglik yoki 
    chuqurlikda bosib oʻtish uchun asosiy algoritmlarni amalga oshirish 
    uchun ham eng qulay usuldir, bu yerda siz hozirda koʻrib chiqilgan 
    uchning "qoʻshnilarini" tezda olishingiz kerak. 
    Koʻpgina masalalarni yechishda matritsalar bilan bir qatorda 
    graflarni aks ettirish uchun qirralar roʻyxati (insidentlik roʻyxati) va 
    uchlar roʻyxati (qoʻshnilik roʻyxat) ishlatiladi. Shunday qilib, -rasmda 
    ushbu roʻyxatlar berilgan: 
    5-jadval.
    Qirralar roʻyxati
    6-jadval.
    Uchlar roʻyxati 


    92 
    Qirralarning roʻyxatida har bir oxirgi uch juft uchlar bilan 
    ifodalanadi, qoʻshnilik roʻyxatida esa har bir uch uchun unga qoʻshni 
    boʻlgan barcha uchlar koʻrsatiladi. Agar har bir ustunda ikkala birlikni 
    tegishli uchlar (qatorlar) belgisi bilan almashtirsak va nollarni olib 
    tashlasak qirralarning roʻyxati insidentlik matritsasining ixcham yozuvi 
    deb taxmin qilishimiz mumkin boʻladi. Xuddi shunday agar har bir 
    satrda boʻlgan birlar mos keladigan uchlar (ustun) belgisi bilan 
    almashtirilsa va nollar olib tashlansa, qoʻshnilik matritsasidan uchlar 
    roʻyxatini olish mumkin. 

    Download 4,61 Mb.
    1   ...   57   58   59   60   61   62   63   64   ...   111




    Download 4,61 Mb.
    Pdf ko'rish

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    -rasm. Yoʻnaltirilmagan grafda insidentlik matritsasi

    Download 4,61 Mb.
    Pdf ko'rish