• Bogʻlangan graf
  • Daraxtlar va zanjirlar.
    		•

    Yoʻlning (yoki siklning) uzunligi




    Download 0.93 Mb.
    Pdf ko'rish
    bet4/9
    Sana12.05.2023
    Hajmi0.93 Mb.
    #58912
    1   2   3   4   5   6   7   8   9
    Bog'liq
    KL-INYAZ ishchi, biblografiya Xudoyberdiyeva 08.02, analitik kim fanini oqitishda ilgor pedagogik texnologiyalardan fojdalanish, 8-Mavzu Mustaqillik yillarida O‘zbekistondagi ma’naviy va madan, BLI Gavhar, маъруза-4.1, Mavzu Suҳbat metodi turlari va unga qo’yiladigan asosiy talabl-fayllar.org, 9FH9EUiDJpSci4iInjwn organized, fizikani-o-qitishda-integrativ-texnologiyalardan-foydalanib-o-quvchilarning-ijodiy-tafakkurini-rivojlantirish-metodikasi, 1 topshiriq (1), Domna ishlab chiqarishi - Vikipediya (1), qalam ihchi 3 курс 2023 й, 1 laboratoriya Mavzu Tarmoq qurilmalarida dastlabki xavfsizlik (1), Mavzu ospf, rip, eigrp va bgp protokollari asosida dinamik ma
    Yoʻlning (yoki siklning) uzunligi uni tashkil etuvchi qirralarning 
    soni deyiladi 
    Agar uning qirralari takrorlanmasa, yoʻl (yoki sikl) oddiy deb 
    nomlanadi; agar u sodda boʻlsa va undagi tepaliklar takrorlanmasa u 
    elementar deb nomlanadi. 
    Graf turlari. Yoʻnaltirilgan graf - (qisqacha orgraf) - qirralari 
    yoʻnaltirilgan graf (4-rasm pastga qarang). 
    Yoʻnaltirilmagan graf - uchlar juftligi tartiblanmagan graf (22-
    rasm) 
    Bogʻlangan graf - bu har qanday uch juftligi oʻrtasida kamida bitta 
    yoʻl mavjud boʻlgan graf. 
    Daraxt - bu bogʻlangan asiklik grafik, ya‘ni sikllar yoʻq va tepalik 
    juftligi orasida bitta yoʻl bor (18-rasm). Kirishning nol darajasiga ega 
    boʻlgan uch daraxtning ildizi, chiqish nol darajaga ega tugunlar esa 
    barglar deb nomlanadi. 
    Bogʻlangan va bogʻlanmagan graflar. 16-rasmda koʻrsatilganlar 
    graflarni ikki guruhga boʻlish mumkin (kesilgan chiziq bilan ajratilgan): 
    bogʻlanmagan (
    ) va bogʻlangan (
    ). 
    Bogʻlanmagan graflarda qirralar bilan ulanmagan ikki yoki undan 
    ortiq qismlar mavjud boʻladi. Ushbu qismlar bogʻlanish komponentlari 
    deb ataladi.
    Yuqorida keltirilgan graflarda 
    da toʻrtta komponent, 
    da uchta 
    komponent, 
    da 2 ta komponent mavjud, qolganlarida esa 
    bittadan komponent mavjud. 
    va 
    graflari oʻrtasida 
    grafini 
    alohida ajratib koʻrsatish mumkin, chunki toʻrtinchi darajali graf uchun 
    maksimal sondagi qirralarga ega.

    84 
    Daraxtlar va zanjirlar. Bogʻlangan graflarda minimal miqdordagi 
    qirralar mavjud boʻlsa, (|
    | ) ular daraxtlar sinfini tashkil 
    etadi. Yuqorida rasmda bu 
    va 
    daraxtga toʻgʻri keladi. Daraxtlar 
    haqida keyingi mavzuda batafsil toʻxtalamiz. Bu yerda biz 16-rasmda
    P4 
    sifatida belgilangan G7 grafini qayd etamiz, bu daraxtning alohida holati 
    va oddiy zanjir deb ataladi. 
    Umuman 
    olganda 
    zanjir 
    – 
    uchlar 
    va 
    qirralarning 
    (
    oʻzgaruvchan ketma-ketligi. Bu yerda 
    va 
    qirraning oxirlari hisoblanadi. Ushbu yozuvni qisqacha 
    shaklda quyidagicha yozishimiz mumkin: 
    yoki 
    . Umumiy turdagi oddiy zanjirdan farqli oʻlaroq, u 
    takrorlanadigan uchlarni oʻz ichiga olishi mumkin. Masalan, quyida 
    keltirilgan 
    graflarda 
    (
    – 
    oddiy 
    zanjir, 
    (
    – zanjir.

    Download 0.93 Mb.
    1   2   3   4   5   6   7   8   9




    Download 0.93 Mb.
    Pdf ko'rish