• Keyingi chekka, uzunligi 6 bolgan DF, xuddi shu usul yordamida takidlangan.
  • Va nihoyat, jarayon 9 uzunlikdagi chekka bilan tugaydi va minimal daraxt daraxti topiladi.
  • Yoyilgan daraxt[ tahrir ]
    		•

    AD va idoralar eng qisqa qirralar bo'lib, uzunligi 5 ga teng va AD o'zboshimchalik bilan tanlangan, shuning uchun u ta'kidlangan




    Download 0.93 Mb.
    bet5/7
    Sana28.07.2023
    Hajmi0.93 Mb.
    #77545
    1   2   3   4   5   6   7
    Bog'liq
    algoritm mustaqil ish
    иш хақи, Mavzu Antivirus-dasturlari, 1-SINF, V sinf texnologiya va dizayn yo‘nalishi buyicha 5-sinflar uchun , Nometal materiallar, Жуфт сузлар, дарс ишланма сон, BEKLEMISHEV KLASSIFIKATSIYASIGA KO, A new generation of realistic writers, Ochiq faoliyat ishlanma 2, Zamonaviy sun, 1-oktyabr oqituvchi va murabbiylar www.sadikov.uz (1)

    AD va idoralar eng qisqa qirralar bo'lib, uzunligi 5 ga teng va AD o'zboshimchalik bilan tanlangan, shuning uchun u ta'kidlangan.

    Idoralar endi tsikl hosil qilmaydigan eng qisqa chekka bo'lib, uzunligi 5 ga teng, shuning uchun u ikkinchi chekka sifatida ta'kidlangan.

    Keyingi chekka, uzunligi 6 bo'lgan DF, xuddi shu usul yordamida ta'kidlangan.

    Keyingi eng qisqa qirralar AB va BE, ikkalasi ham uzunligi 7. AB o'zboshimchalik bilan tanlanadi va ta'kidlanadi. BD qirrasi qizil rang bilan ta'kidlangan, chunki B va D o'rtasida allaqachon yo'l (yashil rangda) mavjud, shuning uchun agar u tanlangan bo'lsa, u tsikl (ABD) hosil qiladi.

    Jarayon keyingi eng kichik chetini ta'kidlashda davom etmoqda, uzunligi 7. Ushbu bosqichda yana ko'plab qirralar qizil rang bilan ta'kidlangan: miloddan avvalgi chunki u tsiklni hosil qiladi miloddan avvalgi, DE chunki u loopni hosil qiladi DEBA, va FE chunki u hosil bo'ladi FEBAD.

    Va nihoyat, jarayon 9 uzunlikdagi chekka bilan tugaydi va minimal daraxt daraxti topiladi.

    To'g'riligini isbotlash[tahrir]

    Dalil ikki qismdan iborat. Birinchidan, algoritm yoyilgan daraxtni ishlab chiqarishi isbotlangan. Ikkinchidan, qurilgan yoyilgan daraxt minimal vaznga ega ekanligi isbotlangan.

    Yoyilgan daraxt[tahrir]

    Minimallik[tahrir]

    Biz quyidagi taklif ekanligini ko'rsatamiz P induksiya orqali to'g'ri: Agar F algoritmning istalgan bosqichida tanlangan qirralarning to'plami, unda minimal daraxt mavjud f va algoritm tomonidan rad etilgan qirralarning hech biri.

    Shubhasiz P boshida to'g'ri, qachon F bo'sh: har qanday minimal daraxt daraxti bajaradi va bitta mavjud, chunki tortilgan ulangan grafik har doim minimal daraxt daraxtiga ega.


    Download 0.93 Mb.
    1   2   3   4   5   6   7




    Download 0.93 Mb.
    Bosh sahifa
    Aloqalar
        Bosh sahifa
    Dərs
    Mühazirə
    Qaydalar
    Referat
    Xülasə
    Yazı


    AD va idoralar eng qisqa qirralar bo'lib, uzunligi 5 ga teng va AD o'zboshimchalik bilan tanlangan, shuning uchun u ta'kidlangan

    Download 0.93 Mb.