Muhammadova layloning

1-lemma («ko'rishishlar» haqida). Ixtiyoriy oriyentirlanmagan grafda barcha uchlar da£^alarijig'indisi qirralar sonining ikki baravariga teng.
Agar grafning uchlar to'plamini o'zaro kesishmaydigan shunday ikki qism to'plamlar (bo'laklar)ga ajratish mumkin bo'lsaki, grafning ixtiyoriy qirrasi bu to'plamlarning biridan olingan qandaydir uchni ikkinchi to'plamdan olingan biron uch bilan tutashtiradigan bo'lsa, u holda bunday graf ikki bp 'lakli graf (bixromatik yoki Kyonig graft), deb ataladi. Ta'rifdan ko'rinib turibdiki^ ikki bo'lakli grafning har bir bo'lagidagi ixtiyoriy ikki uch qo'shni bo'la olmaydi. Biron bo'lagida faqat bir uch bo'lgan to'la ikki bo'lakli graf yulduz, deb ataladi.
Agar ikki bo'lakli graimngturli bo'laklariga tegishli istalgan ikki uchi qo'shni bo'lsa, u holda bu graf to 'la ikki bo 'lakli graf deb ataladi. To'la ikki bo'lakli grafni K_mnbilan belgilaymiz, bu yerda, m van bilan grafning bo'laklaridagi uchlar sonlari belgilangan. K_mn= (V, U) graf uchun | V\=m+n va | V\^mn bo'lishi ravshan, bu yerda | V\ —K_mngrafning uchlari soni, | U[— uning qirralari soni.
Grafning ikki bo'lakli graf bo'lishi haqidagi ba'zi qo'shimcha ma'lumotlar (Kyonig teoremasi) ushbu bobning 4-paragrafida keltirilgan. Ikkidan katta ixtiyoriy natural кson uchun кbo 'lakli graf tushunchasini ham kiritish mumkin.
1-misol. O'zbekistof Respublikasi hududidagi aeroportlar to'plamini Fbilan, shaharlar orasida belgilangan vaqt mobaynida amalga oshirilayotgan sjraio^^yj.rning uchib-qo'nish hodisalarl kortejini U bilan belgilaymiz. U holda (V, U) juftlikni graf, deb qarash mumkin. Bu yerda grafning uchlariga aeroportlar, yoylariga esa samolyotlarning uchib-qo'nish hodisalari mos keladi. Tabiiyki, (V,U) grafda karrali yoylar bo'lishi mumkin, agar qandaydir sababga ko'ra, samolyot uchgan aeroportga qaytib qo'nsa, u holda bu hodisaga qaralayotgan grafdagi sirtmoq mos keladi. \
2-misol. Qadimgi boshqotirma masalalar qatoriga kiruvchi quyidagi masalani qaraymiz. Biron idishdagi hajmi 8 birlik suyuqlikni faqat o'sha idish hamda 5 va 3 birlik hajmli idishlar vositasida teng ikki qismga bo'ling¹. 8, 5 va 3 birlik hajmli idishlardagi suyuqlik hajmini, mos ravishda, a, b va с Man belgilab, muayyan bir vaqt uchun idishlardagi suyuqlikning hajmlari asosida qaralayotgan sistemaning holatini ifodalovchi uchliklarni tuzamiz. Masalaning shartiga ko'ra, a, b vaсo'zgaruvchilar butun qiymatlar qabul qilgan holda 0<#<8,0 < 5 va 0
Holatlar to'plamini V bilan belgilaymiz.Suyuqlikni (yoki uning bir qismini) idishlarning biridan boshqa birontasiga quyish natija-sida sistema bir holatdan boshqa holatga o'tishi mumkiri.Ta'kidlash kerakki, yuqoridagi holatlarning ixtiyoriysidan boshqa birontasiga bevosita yoki bilvosita o'tish imkoniyati mavjud bo'lmasligi ham mumkin.Sistemaning bir holatdan boshqa holatga bevosita o'tishlari to'plamini U bilan belgilaymiz. Natijada hosil bo'lgan (V,U) juftlikni graf, deb qarash mumkin. Bu grafning uchlari sistema holatlariga, yoylari (qirralari) esa, bevosita o'tishlarga mos keladi.
Berilgan masalani hal qilish uchun (V, V) grafning yoylaridan tashkil topgan shunday ketma-ketlik tuzish kerakki, bu ketma-ketlikning birinchi hadi <8,0,0>, oxirgi hadi esa <4,4,0> bo'lsin. Bunday ketma-ketliklardan bin quyida keltirilgan:
<8,0,0>, <5,0,3>, <5,3,0>, <2,3,3>, <2,5,1>, <7,0,1>, <7,1,0>, <4,1,3>, <4,4,0>. ■
Qadim zamonlardan beri Koenigsberg aholisi jumboq bilan kurashib kelishgan: Koenigsbergning barcha ko'priklaridan faqat bir marta o'tib o'tish mumkinmi? Bu muammo nazariy jihatdan ham, qog'ozda ham, amalda ham, xuddi shu ko'priklardan o'tish orqali hal qilindi. Hech kim buni amalga oshirish mumkin emasligini isbotlay olmadi, lekin hech kim ko'priklar bo'ylab bunday "sirli" yurish qila olmadi.
1736 yilda mashhur matematik, Sankt-Peterburg Fanlar akademiyasining a'zosi Leonard Eyler ettita ko'prik masalasini hal qilishni o'z zimmasiga oldi. O'sha yili u bu haqda muhandis va matematik Marioniga yozgan. Eyler shunday qoida topdiki, unga ko‘ra barcha ko‘priklardan o‘tish mumkinmi yoki yo‘qmi, shu bilan birga ularning hech biridan ikki marta o‘tmaslik mumkinligini hisoblash qiyin emas. Koenigsbergning etti ko'prigida buni qilish mumkin emas.
Aynan shu ko'prik muammosi tufayli eski Königsberg xaritasida yana bir ko'prik paydo bo'ldi, uning yordamida Lomse oroli janubiy tomonga ulangan. Bu shunday sodir bo'ldi. Imperator (Kaiser) Vilgelm o'zining oddiy fikrlashi, tezkor reaktsiyasi va askarning "torligi" bilan mashhur edi. Kayzer ishtirok etgan ziyofatlardan birida taklif etilgan olimlar u bilan hazil o'ynashga qaror qilishdi: Vilgelmga ko'priklar muammosini hal qilishni taklif qilgan Kenigsberg xaritasi ko'rsatildi. Vazifani hal qilib bo'lmas edi. Vilgelm hammani hayratda qoldirib, muammoni hal qilish mumkinligini va uni bir necha daqiqada hal qilishini e'lon qilib, qog'oz va qalam talab qildi. Qog'oz va siyoh topildi, ammo hech kim Kayzer Vilgelmda bu muammoni hal qilganiga ishonolmadi. Taqdim etilgan qog'ozga kayzer shunday deb yozgan: "Men Lomse orolida sakkizinchi ko'prikni qurishni buyuraman". Yangi ko'prik Imperator ko'prigi yoki Kayzer-bruk deb nomlangan.
Ushbu sakkizinchi ko'prik ko'prik vazifasini hatto bola uchun ham oson qiziqarli qildi....
Koenigsberg - Rossiyaning eng g'arbiy mintaqasining markazi, yumshoq iqlimi, plyajlari va amber mahsulotlari bilan mashhur Kaliningradning tarixiy nomi. Kaliningrad boy madaniy merosga ega. Bu erda ular bir vaqtlar yashab, ishlagan buyuk faylasuf I. Kant, hikoyachi Ernst Teodor Amadeus Hofman, fizik Frans Neyman va boshqa ko'plab kishilarning nomlari fan va ijod tarixiga kiritilgan. Qiziqarli muammo Koenigsberg ko'priklari muammosi deb ataladigan Koenigsberg bilan bog'liq.