Muhammad al-xorazmiy nomidagi Toshkent axborot texnologiyalri universiteti 2-kurs talabasi bo’riyev husanning diskrit tuzilmalar fanidan yozgan Mustaqil ishi Bajardi: Bo’riyev husan Tekshirdi: Begimov o’ktam

Ko‘ndalangiga izlash usuliga ko‘ra, grafning uchlari 0,1,2,3,... raqamlar bilan quyidagi qoida bo‘yicha belgilanadi. Dastlab grafning ixtiyoriy uchi 0 raqami bilan belgilab olinadi. Shu 0 belgili uchga qo‘shni barcha uchlarga 1 belgisi qo‘yiladi. Endi 1 belgili har bir uchga qo‘shni uchlami aniqlab, ular orasidagi belgisi yo‘q uchlarga 2 belgisini qo‘aymiz. Keyin 2 belgisiga ega barcha uchlami aniqlab, ular uchun ham yuqoridagiga o‘xshash ish yuritamiz. Bu jarayonni mumkin bolgan qadar davom ettiramiz. Tushunarliki, agar G graf boglamli bolsa, u holda ko‘ndalangiga izlash usuli grafning barcha uchlarini raqamlab chiqish imkonini beradi.

Eyler graflari. Graflar nazariyasining shakllanishi Kyonigsberg ko‘priklari haqidagi masala bilan bog‘liq ekanligi yaxshi ma’lum. L. Eyler 1736-yilda bu masalaning yechimga ega emasligini isbotladi. U graflar nazariyasining ancha umumiy hisoblangan quyidagi savoliga ham javob topdi: qanday shartlar bajarilganda, bog‘lamli grafda barcha qirralardan faqat bir marta o‘tadigan sikl mavjud boMadi? Grafning har bir qirrasidan faqat bir marta o‘tadigan zanjir Eyler zanjiri, deb ataladi. Yopiq Eyler zanjiriga (ya’ni Eyler sikliga) ega graf Eyler graft, deb ataladi. Agar grafda yopiq bo‘lmagan Eyler zanjiri topilsa, u holda bunday graf yarim Eyler graft, deb ataladi. 1-teorema. Bog‘lamli graf Eyler graft bo‘lishi uchun undagi barcha uchlaming darajalari juft bo‘lishi zarur va yetarlidir.

Isboti. Zarurligi. G Eyler graflda C — Eyler sikli bo‘lsin. U holda С sikl bo‘ylab harakatlanganda grafning har bir uchidan o‘tish uchun bir juft qirradan foydalaniladi — bu qirralardan biri uchga kirish uchun, ikkinchisi esa uchdan chiqish uchun zarur bo‘ladi. Bu yerda har bir uch darajasining juftligi С sikldagi har bir qirraning bir marta uchrashi mumkinligidan kelib chiqadi. Yetarliligi. Endi G grafning har bir uchi darajasi juft bo‘lsin, deb faraz qilamiz. G graf bog‘lamli bo‘lgani uchun undagi har bir uchning darajasi ikkidan kichik emas. Ma’lumki, agar grafda har bir uchning darajasi ikkidan kichik bo‘lmasa, u holda bunday graf tarkibida sikl mavjud (ushbu bobning 4-paragrafidagi 1-teoremaga qarang). Demak, G grafning qirralaridan tashkil etilgan qandaydir Cj sikl bor. Bu siklni uning ixtiyoriy Vj uchidan boshlab quramiz. Dastlab v, uchga insident bolgan ixtiyoriy bir qirrani tanlab, bu qirra bo‘ylab harakatlanamiz va uning boshqa uchiga o‘tamiz. Har safar, imkoniyati boricha, yangi qirra tanlab va bu qirradan o‘tib, uning boshqa uchiga boramiz. Shuni ta’kidlash zarurki, bunday o‘tishlar jarayonida faqat qirraning yangisini tanlashga harakat qilinadi, uchlar esa istalgancha takrorlanishi mumkin.