Graflar ustida bir quvish va qochish masalasi haqida

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

Bu yerda , , , koordinatalarda joylashgan ishtirokchilarga nisbatan teorema 2 ning qo’llanilishi tekshirib ko’ramiz:
Qochuvchi x o’qiga parallel yuqoriga harakatlansin deb faraz qilaylik. Uning uchun teorema 2 dagi shartni qanoatlantirilishini tekshirib ko’ramiz:
| |-| - |=
Demak qochuvchi x o’qiga parallel ga tomon harakatlanganida yutuqga ega emas.
Endi ga tomon harakatlansa nima bo’lishini ko’rib chiqaylik :
| |-| - |=
Demak x o’qiga parallel o’ngga harakatlanganida ham yutuqga ega emas ekan.
Teoremalar isbotlandi.
Endi biz quvuvchilar tashkil qilgan sohadagi tugun nuqtalarning qaysilarida qochuvchi cheksiz qochish imkoniyatiga ega bo’ladi yana qaysilarida esa yo’q, shu savollarga javob beramiz.
Graflarda quvuvchilar joylashishiga qarab o’tkir, o’tmas va to’g’ri burchakli uchburchaklar hosil bo’lishi mumin (quvuvchilar uchta bo’lgan holda).
Biz bu bobda quvuvchilarning qochish imkoniyatlari mavjud bo’lgan nuqtalarni ko’rib chiqamiz. Aytaylik bizga quvuvchilar quyidagi korinishda joylashgan bo’lsin:

1-rasm
quyidagi ko’rinishda:

2-rasm
yoki bunday:

3-rasm
Agar biz birlik kvadratda joylashgan quvuvchilarning uchburchak sohada joylashgan diagonal nuqtalarini belgilab chiqsak 1-rasmdagidek holat yuzaga keladi. Ana shu diagonal nuqtalar qochuvchi uchun yutuqsiz nuqtalar hisoblanar ekan. Sababi ular 1-rasmdagidek qilib ikkita perpendikulyar chiziqlar o’tkazsak diagonal nuqtalarning har biri qaysi quvuvchining diagonal nuqtasi bo’lsa o’sha quvuvchi bilan ikki yo’nalish bo’yicha chegaralanganligi ko’rinib qoladi. Qolgan ikkita yo’nalish bo’yicha harakatning yutuqsiz ekanligini tekshirish qoladi holos. Bunday diagonal nuqtalarning barchasi ham yutuqsiz bo’lavermas ekan. Agar diagonal nuqtalar 1-rasmdagidek ikkita bo’lsa ular o’zaro kesishadi va ularning kesishish nuqtalarigacha bo’lgan nuqtalar qochuvchi uchun yutuqsiz bo’ladi qolganlari esa quvuvchi uchun yutuqlidir. Agar diagonal nuqtalar 2- rasmdagidek bitta bo’lib u uchburchak sohaning o’tmas burchagidan chiqsa uchburchak sohaning barcha tugun nuqtalari qochuvchi uchun yutuqli bo’lar ekan. Agar diagonal nuqtalar 3-rasmdagidek uchburchak sohaning o’tkir burchagidan chiqsa unda bu diagonal nuqtalarning barchasi qochuvchi uchun yutuqsiz hisoblanadi. Yoki diagonal nuqtalar 4-rasmdagidek umuman bo’lmasligi mumkin.
Yuqoridagi to’rtta rasmga qarab qochuvchining qochish imkoniyatini bemalol baholash mumkin qachon, qachonki soha yetarlicha kichik bo’lsa agar soha kata bo’lsa ushbu | - |-| |>0 , | |-| - |>0 ikki tengsizlik yordamida qochish yo’nalishini aniqlab harakatni o’sha tomonga qarab qilish yetarli holos.