5- §. Eyler va Gamilton1 graflari

3- teorema (Ore). Agar uchlari soni ga ( ) teng bo‘lgan grafdagi qo‘shni bo‘lmagan ixtiyoriy uchlar darajalari yig‘ndisi dan kam bo‘lmasa, u holda bu graf Gamilton grafi bo‘ladi.
Isboti o‘quvchiga topshiriq sifatida beriladi.
2 - misol. 3- shaklda tasvirlangan graflar Gamilton graflariga misol bo‘la oladilar. Bir qarashdayoq sezish mumkinki, bu graflarning har birida bir nechtadan Gamilton sikllari mavjud. Mumkin bo‘lgan ba’zi Gamilton sikllari shaklda qalin chiziqlar bilan ifodalangan. ■
3
- misol. Shaxmat o‘yinidagi otning yurishi haqidagi Eyler masalasi deb ataluvchi quyidagi masalani qaraymiz. Shaxmat taxtasidagi istalgan katakda turgan shaxmat oti uchun yurishlarning shunday ketma-ketligini tuzingki, u barcha kataklardan faqat bir martadan o‘tsin va yurish boshlangan katakka qaytib kelsin. Bu masalani hal qilish maqsadida tuzilgan graf (shaxmat taxtasidagi kataklarga grafning uchlari, otning yurishlariga esa uning qirralari mos qo‘yilishi nazarda tutilmoqda) ham Gamilton grafiga misol bo‘la oladi. Bu masalaning yechimlaridan biri 4- shaklda keltirilgan. ■
4- misol. 5- shaklda tasvirlangan grafda Gamilton zanjiri mavjud emas. ■
B erilgan grafda Gamilton zanjirining mavjudligi shartlarni o‘rganish bo‘yicha izlanishlar davom etayotganligi va bu sohadagi ishlar bugungi kunda ham dolzarbligini yo‘qotmaganligi yuqorida qayd etilgan edi. Grafdagi uchlar soni ning qiymatiga nisbatan ko‘phad bilan chegaralangan sondagi qadam ishlatib istalgan grafda Gamilton zanjiri mavjudligini tekshiradigan algoritm hozirgacha topilmagan. Shuning uchun ham Gamilton zanjirini topish masalasi graflar nazariyasida markaziy masalalardan biri bo‘lib qolmoqda, Albatta, grafdagi ta uchlarning ta turli ketma-ketliklarini (aniqrog‘i, takrorlanmaydigan o‘rin almashtirishlarini) tuzib grafda Hamilton zanjiri mavjudligi masalasini hal qilish mumkin. Shunday bo‘lishiga qaramasdan, barcha ta o‘rin almashtirishlarini bajarmasdan qadamlar sonini jiddiy qisqartiradigan umumiy algoritm bor.
Grafda Gamilton zanjirini topish masalasi quyidagi kommivoyajer⁶ masalasi deb ataluvchi masalada oshkora namoyon bo‘ladi. Bir-birlari bilan yo‘llar (graf qirralari) vositasida bog‘langan shaharlar (graf uchlari) tarmog‘i berilgan bo‘lib, shaharlarning har bir jufti uchun masofa (uni bilan belgilaymiz) mos qo‘yilgan hamda o‘zaro bog‘lanmagan shaharlar orasidagi masofa cheksiz katta deb hisoblaymiz. Kommivoyajer uchun shunday Gamilton sikli to-pish kerakki, ifodaning qiymati minimal bo‘lsin, bu yerda – tarmoqdagi - shahar ( ). Boshqacha aytganda, kommivoyajerning biror shahardan chiqib va qolgan barcha shaharlardan faqat bir martadan o‘tib, yana dastlabki shaharga qaytishi imkonini beruvchi eng kichik umumiy uzunlikka ega bolgan yo‘lni topish kerak.