Zahiriddin muhammad bobur nomidagi andijon davlat universiteti fizika matematika fakulteti

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.