Graflar ustida bir quvish va qochish masalasi haqida

M isol. Aytaylik, bizga ishtirokchilarning
grafdagi boshlang’ich holati ushbu
ko’rinishda berilgan bo’lsin:

Bu yerda , , , koordinatalarda joylashgan ishtirokchilarga nisbatan teorema 1 ning qo’llanilishi tekshirib ko’ramiz:
Qochuvchi y o’qiga parallel yuqoriga harakatlansin deb faraz qilaylik. Uning uchun teorema 1 dagi shartni qanoatlantirilishini tekshirib ko’ramiz:
| - |-| |=|2-(-2)|-|7-5|>0
shart bajariladi.
Demak qochuvchi yuqoriga qarab harakatlanganida cheksiz qochish imkoniyatiga ega.
Endi y o’qiga parallel pastga harakatlansin deb faraz qilaylik:
| - |-| |=|2-2|-|-2-5|<0 tengsizlik manfiy qiymat qabul qiladi va qochuvchining ushbu yo’nalishda harakatlanishda yutuqga ega emas. Haqiqatdan ham shunday ekanligini chizmadan ko’rib olish qiyin emas. Sababi yuqriga qarab yurganda o’sha biz yuqorida aytgan qadamlar soni qochuvchida kamroq.
Teorema 2. = boshlang’ich holatda turgan qochuvchi, boshlang’ich holatlari koordinatalarda bo’lgan quvuvchilar qurshovidan o’qiga parallel ravishda harakatlanganida Ǝ topilib, ushbu | |-| - |>0 shart bajarilganida cheksiz qochish imkoniyatiga ega bo’ladi va o’yin qochuvchi foydasiga hal bo’ladi, aks holda quvuvchilar o’yinda g’olib bo’ladi.
Isbot. Ushbu o’yinda qochuvchilar qancha o’yinni cho’zishga harakat qilishsa, quvuvchilar shuncha o’yinni tez tugatib o’z foydasiga hal qilinishini ko’zlashadi. Shunday ekan biz qochuvchi uchun shunday qisqa masofani topishimiz kerak ekanki (agar u mavjud bo’lsa) shu masofadan so’ng ixtiyoriy ta’qibi cheksiz davom etsin. Yuqoridagi teoremada ham shu nazariya qo’llanib tengsizlik keltirilgan.
Aytaylik yana ishtirokchilarning boshlang’ich holatlari quyiyidagi ko’rinishda berilgan bo’lsin:

Biz o’yinni boshlanishini yuqoridagi rasmdagidek tasavvur qildik. Qochuvchi boshlang’ich holatiga nisbatan to’rt hil boshqaruv qo’llashi mumkin. Bularning ikkitasi y o’qiga parallel bo’lsa, qolgan ikkitasi x o’qiga parallel bo’ladi. Demak ning boshlang’ich holatiga nisbatan yuqoriga qarab yurganida va quvuvchilarning ta’qibidan qutulishi, o’ngga qarab yurganida ning ta’qibidan, chapga qarab yurganida va larning ta’qibidan, pastga qarab yurganida ning ta’qibidan qutilishi lozim boladi. Ularning taqibidan qutilish uchun shunday qisqa masofaga tezlik bilan quvuvchilardan oldin yetishi kerakki, shu masofadan so’ng ta’qib qiluvchu quvuvchilar yo ortta yoki bo’lmasa parallel harakat qilishsin. Shundan so’nggina o’yin cheksiz davom etib shart hech qachon bajarilmaydi. Buning uchun qochuvchi yuqoriga qarab yurganida A nuqtadan so’ng, o’ngga qarab yurganida C nuqtadan so’ng, chapga qarab yurganida B nuqtadan so’ng, pastga qarab yurganida D nuqtadan so’ng ortta qolishi yoki parallel yurishi ma’lum. Lekin, o’yinda kim g’olib bo’lishini shu nuqtalarga kim birinchi yetib kelishi hal qilar ekan. Agar ushbu nuqtalarga birinchi bo’lib qochuvchi yetib kelsa o’yinda qochuvchi aks holda esa quvuvchilar g’olib bo’ladi. Yuqoridagi ushbu | |-| - |>0 tengsizlik ham qochuvchi x o’qiga parallel harakatlanganida B va C nuqtalarga kim birinchi yetib borishi korsatilgan. Bunda va larning B va C nuqtalarga yetib borish qadamlari sonidan ning yetib borish qadamlari sonidan kichik bo’lsa qochuvchi yutishi ko’rsatilgan. Agar qochuvchi chapga qarab harakatlanganida ham shu amaliyot ya’ni masofa ro’l o’ynashi hisobga olingan va shu masofaga qarab o’yinda qaysi tomon yutishi ko’rsatilgan.