• Sodda grafilar uchun xotiradan foydalanish O(|V|+|E|) O(|V| 2 ) Graflarda oʻtish
  • -jadval. Qoʻshnilik matritsasi va roʻyxatining algoritmlarda




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

    7-jadval.
    Qoʻshnilik matritsasi va roʻyxatining algoritmlarda 
    bajarilishini taqqoslash 
    Amal 
    Qoʻshnilik 
    roʻyxati 
    Qoʻshnilik 
    matritsasi 
    (x,y) qirraning mavjudligini 
    tekshirish 
    O(|V|+|E|) 
    O(1) 
    Qirraning darajasini hisoblash 
    O(1) 
    O(|V|) 
    Sodda grafilar uchun xotiradan 
    foydalanish 
    O(|V|+|E|) 
    O(|V|
    2

    Graflarda oʻtish 
    O(|V|+|E|) 
    O(|V|
    2

    Mavzu yuzasidan savollar: 
    1.
    Graflarning umumiy ta‘rifini bering. 
    2.
    Grafning eng asosiy tushunchalariga toʻxtalib oʻting 
    3.
    Qoʻshnilik roʻyxati va qoʻshnilik matritsasini hosil qilish 
    jarayonini tushuntirib bering 
    4.
    Insidentlik matritsasi qanday hosil qilinadi? 
    5.
    Graflar qoʻllaniladigan sohalarni sanang. 
    Mustaqil ishlash uchun masalalar: 
    Quyida berilgan graflar boʻyicha berilgan vazifalarni hal qiling: 


    93 
    1)
    Berilgan grafning barcha tushunchalarini keltiring (uchlar, qirralar, 
    grafning yoʻnalishga ega yoki yoʻqligi boʻyicha aniqlanishi, 
    yakkalangan uch mavjudligi, regular yoki regular emasligi va 
    hokazo). 
    2)
    Grafni mashina xotirasida tasvirlash 
    3)
    Grafni uchlar qoʻshniligi matritsasi orqali tasvirlang 
    4)
    Grafni qoʻshnilik roʻyxati orqali tasvirlash 
    5)
    Grafning insidentlik matritsasi orqali tasvirlash 
    a) b) 
     
     
     
     
     
     
     
     
     
     
     
     
     
    c)
     
     
     

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




    Download 4,61 Mb.
    Pdf ko'rish

    Bosh sahifa
    Aloqalar

        Bosh sahifa



    -jadval. Qoʻshnilik matritsasi va roʻyxatining algoritmlarda

    Download 4,61 Mb.
    Pdf ko'rish