Zahiriddin muhammad bobur nomidagi andijon davlat universiteti fizika matematika fakulteti




Download 278.71 Kb.
bet4/5
Sana30.03.2023
Hajmi278.71 Kb.
#47635
1   2   3   4   5
Bog'liq
Ibroximbek kurs ishi
3, Hujjat (4) (3), 7.WORD MAT MUHARRIRIDA FORMULALAR BILAN ISHLASH, Moliyaviy hisobot tuzish qoidalari va ularning mohiyati, Furqat indivudual, Diqqatning turlari va uning xususiyatlari, Hujjat (4), Mavzu Pnevmatik porshenli va silfonli ijro mexanizmlarini hisob, Mavzu “3-sinf matematika darslarida axborot texnologiyalaridan , Arxivlash dasturlari Fayllarni arxivlash va arxiv fayllarni ochish, 2 5335036374535907644, Boshqarish tizimlarini loyihalash, Kimyo injiniringida modellashtirish va avtomatlashtirish fanidan, T. Shomurodov - Texnologik jarayonlar va qurilmalarni hisoblash va loyihalash
Teorema: Muntazam grafik n-ketma-ketlik bog'langan grafik orqali amalga oshirilishi mumkin, agar va faqat va
(1)
Agar bu shartlar bajarilsa, u holda l-protsedura, uning har bir bosqichida minimal musbat yorliqli yetakchi cho'qqi bog'langan grafikga olib keladi. Izoh uchun (1) tengsizlik avtomatik ravishda bajariladi.
Teorema shartlarining zarurligi aniq. Darhaqiqat, n-tartibdagi bog'langan grafaning izolyatsiyalangan uchlari yo'q va undagi qirralarning soni kamida n-1 ni tashkil qiladi. Tengsizlik (1) qo'l siqish lemmasidan kelib chiqadi.
Ketma-ketlikni d uzunligi bo'yicha induksiya yo'li bilan etarliligini isbotlaymiz. n=2 uchun faqat bitta ketma-ketlik teorema shartlarini qanoatlantiradi. Ushbu ketma-ketlikning amalga oshirilishi bog'langan grafikdir, shuning uchun n=2 uchun teorema to'g'ri bo'ladi. Endi n>2 bo'lsin va isbotlanayotgan tasdiq uzunliklari n dan kichik bo'lgan grafik ketma-ketliklar uchun to'g'ri bo'lsin. Keling, ikkita holatni alohida ko'rib chiqaylik:
1) n>2 bo'lgani uchun (1) tengsizlikdan kelib chiqadiki. Olingan ketma-ketlikni ko'rib chiqamiz

i=


Chunki u holda ketma-ketlik teorema shartlarini qanoatlantiradi.
2) Yana ikkita holatni ajratamiz:
a) va b).
a) vaziyatda teorema shartlaridan kelib chiqadiki
Ixtiyoriy ketma-ketlik uchun bizda bor

b) vaziyatda ixtiyoriy ketma-ketlik uchun biz olamiz

Shunday qilib, har qanday vaziyatda olingan ketma-ketlik teorema shartlarini qanoatlantiradi va induktiv farazga ko'ra, l-protsedura teoremasining bayonidagi tavsiflar natijasida olingan H bog'liq realizatsiyaga ega bo'ladi. H grafigiga darajalar cho'qqilariga qo'shni yangi cho'qqi qo'shsak, biz d ketma-ketlikning bog'langan realizatsiyasini olamiz.


Xuddi shunday isbotlangan

Teorema: n-ketma-ketlik d daraxt tomonidan amalga oshirilishi mumkin, agar unda nol bo'lmasa va tenglik to'g'ri bo'lsa.
Belgilangan shartlar bajarilsa, l-protsedura, agar har bir bosqichda biz eng kichik musbat yorliqli cho'qqini etakchi cho'qqi sifatida tanlasak, ketma-ketlikning daraxt bajarilishini quradi.
5-rasmda ketma-ketlikning amalga oshirilishi bo'lgan daraxtni yaratadigan protsedurani ko'rsatadi.

5-rasm.
Keling, chekka ulanishi ko'proq bo'lgan grafiklarga o'tamiz. Quyidagi teoremani isbotsiz keltiramiz.

Download 278.71 Kb.
1   2   3   4   5




Download 278.71 Kb.

Bosh sahifa
Aloqalar

    Bosh sahifa



Zahiriddin muhammad bobur nomidagi andijon davlat universiteti fizika matematika fakulteti

Download 278.71 Kb.