Mustaqil ish

Teorema. Agar grafdagi har bir uchning lokal darajasi ikkidan kichik bo’lmasa, u holda bu graf tsiklga ega.

Isboti.Agarda graf sirtmoqlar yoki karali qirralardan iborat bo’lsa, teoremaning isboti ravshan. Shu sababli teorema isbotini graf karrali qirralar va sirtmoqlar bo’lmagan holda keltiramiz.

Faraz qilaylik, berilgan grafning ixtiyoriy uchi bo’lsin. Qaralayotgan uchga qo’shni uchni va bu uchga dan farqli boshqa qo’shni uchni uchga esa dan farqli boshqa uchni va hakozo, uchga dan farqli boshqa qo’shni uchni va hakazo, tanlab,

qirralar ketma-ketligini tuzamiz. Teoremaning shartiga ko’ra yuqoridagi ketma-ketlikni tuzish va talab etilgan hossaga ega uchni har doim topish mumkin.

Grafning uchlar to’plami chekli to’plam bo’lganligidan, yuqorida bayon etilgan uchlar ketma–ketligini qurish jarayonida chekli qadamdan so’ng albatta oldin uchragan uchlardan birini tanlashga majburmiz. Agar biror uch ketma–ketlkda ikki marta uchragan birinchi uch bo’lsa, ketma–ketlikka qirralar qo’shish jarayonini to’xtatamiz., chunki tuzilgan qirralar ketma–ketligining uch ikki marta qatnashgan qismi biz izlayotgan tsikldir. Teorema isbot bo’ldi.

graf yo’naltirilmagan graf bo’lsin. Agar oxirlari va uchlardan iborat (3.1) ko’rinishdagi marshrut marshrut mavjud bo’lsa, u holda ikkita va uchlar bog’langan deyiladi. Agar marshrut qandaydir uchdan bir martadan ko’p o’tsa, u holda uning tsiklik qismini o’chirib tashlash orqali, va uchlarni bog’lovchi qirralardan iborat yangi marshrut hosil qilinadi. Bundan kelib chiqadiki, marshrut bilan bog’langan uchlar doimo oddiy zanjir bilan ham bog’langan bo’ladi. Agar grafda uning ixtiyoriy ikki uchi bog’langan bo’lsa, bu holda uni bog’lamli graf deb ataladi.

Agar ixtiyoriy grafda uch uch bilan, uch esa uch bilan bog’langan bo’lsa, u holda ko’rinib turibdiki, uch uch bilan bog’langan bo’ladi. grafning uchlar to’plami uchun juft–jufti bilan kesishmaydigan quyidagicha (3.4) yig’indi mavjud. Bunda har bir qism to’plamdagi uchlar o’zaro bog’langan, turli qism to’plamdagi uchlar o’zaro bog’lanmagan bo’ladi. Mos ravishda (3.4) yig’indidan grafning qism graflari kesishmaydigan quyidagicha (3.5) to’g’ri yig’indisi tuziladi. Bu qism graflar grafning bog’lamlilik komponentalari deyiladi. Yuqorida keltirilgan tasdiqlardan quyidagicha teoremani isbotsiz keltiramiz.