Graflar ustida bir quvish va qochish masalasi haqida

II bob bo’yicha xulosa
Tekislikda ko’riladigan differensial o’yinlarning barchasi ham graflar ustida ko’rilganida bajarilavermas ekan. Tekislikda ko’rilganda qurshovda bo’lgan quvuvchining cheksiz qochib yura olish imkoniyati yo’q bo’lsa, graf ustida qaralganda ba’zi hollarda uning cheksiz qochib yura olish imkoniyati mavjud ba’zi hollarda esa mavjud emas ekan.

III BOB. ASOSIY TEOREMA VA ISBOTLAR
3.1§ Masalaning qo’yilishi
Endi biz quvuvchi va qochuvchilarning boshlang’ich holatlariga turli cheklovlar qo’yilganda o’yin kimning foydasiga hal bo’lishini ko’rib chiqaylik. Biz bu bobda quyidagicha masalalarni ko’rib chiqamiz:
Aytaylik quvuvchilar soni uchta bo’lib qochuvchi quvuvchilar qurshovida bo’lsin. U holda quvuvchining qochish imkoniyatlari qanaqa va qanday harakatlanganida cheksiz qochish imkoniyatiga ega bo’ladi?
Agar quvuvchilar soni 3 tadan ortiq bo’lsa yoki n (n ) ta ga teng bo’lgan holda qochuvchining qochish imkoniyatlari qanday?
Yuqoridagi ikkita holatda qochuvchi quvuvchilar hosil qilgan qavariq ko’pburchakning qanday tugun nuqtalarida bo’lganida cheksiz qochis imkoniyatiga ega bo’ladi qanday nuqtalarida bo’lganida qochib keta olmaydi ya’ni o’yin quvuvchilar foydasiga hal bo’ladi?
Biz sizlarga quyida quvuvchi va qochuvchilarning graflarda joylashish hollariga bir nechta misollar keltirib o’tamiz

Yuqorida keltirilgan rasmlarda quvuvchi va qochuvchilarning boshlang’ich holatlariga turli shartlar qo’yilgan ya’ni quvuvchilarga qochuvchini o’rab turish, qochuvchi esa quvuvchilar qurshovida bo’lishi shartlari ko’rsatib o’tilgan.

Izlanishlar natijasida shu ma’lum bo’ldi-ki quvuvchilar qochuvchini o’rab turgan holatda ham qochuvchining qochish imkoniyati mavjud ekan. Biz anashunday nuqtalar qayerda va qanday shartlar bajarilganda qochuvchini qochish imkoniyati mavjud bo’lishini ko’rsatib o’tamiz.
Teorema 1. = 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 ishtirokchilarning boshlang’ich holatlari quyidagi 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 ortda yoki bo’lmasa parallel harakat qilishsin. Shundang so’nggina o’yin cheksiz davom etib hart 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 ortda 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 y o’qiga parallel harakatlanganida A va D nuqtalarga kim birinchi yetib borishi ko’rsatilgan. Bunda va larning A va D nuqtalarga yetib borish qadamlari sonidan ning yetib borish qadamlari sonidan kichik bo’lsa qochuvchi yutishi ko’rsatilgan. Agar qochuvchi pastga qarab harakatlanganida ham shu amaliyot yani masofa ro’l o’ynashi hisobga olingan va shu masofaga qarab o’yinda qaysi tomon yutishi ko’rsatilgan.