Siklik graflarda o‘yinlar

Ikki o‘yinchi ixtiyoriy $G$ grafida o‘yin o‘ynasin. Ya’ni o‘yinning joriy holati ma’lum bir cho‘qqidir. O‘yinchilar navbatma-navbat yurishlarni bajaradilar va joriy cho‘qqidan unga tutash cho‘qqiga bog‘lovchi qirra orqali o‘tadilar. O‘yinga qarab, yura olmay qolgan kishi o‘yinda yutqazishi yoki yutishi mumkin.

Biz eng umumiy holatni, ya’ni sikllarga ega ixtiyoriy yo‘naltirilgan graf holatini ko‘rib chiqamiz. Bizning vazifamiz — berilgan boshlang‘ich holat uchun, agar ikkala o‘yinchi ham optimal strategiyalar bilan o‘ynasa, kim yutishini aniqlash yoki o‘yin natijasi durang bo‘lishini aniqlash.

Biz bu masalani juda samarali yechamiz. Grafning barcha mumkin bo‘lgan boshlang‘ich cho‘qqilari uchun yechimni qirralar soniga nisbatan chiziqli vaqt ichida topamiz: $O(M)$ .

Algoritm tavsifi

Agar o‘yinchi ushbu holatdan boshlab optimal o‘ynasa (raqib qanday yurishlar qilmasin), o‘yinni yutsa, u holda cho‘qqini yutuvchi cho‘qqi deb ataymiz. Xuddi shunday, agar o‘yinchi ushbu cho‘qqidan boshlab o‘ynasa va raqib optimal o‘ynaganda yutqazsa, u holda cho‘qqini yutqazuvchi cho‘qqi deb ataymiz.

Grafning ayrim cho‘qqilari uchun biz oldindan ularning yutuvchi yoki yutqazuvchi cho‘qqi ekanini bilamiz: xususan, chiqish qirralari bo‘lmagan barcha cho‘qqilar.

Shuningdek, bizda quyidagi qoidalar bor:

agar cho‘qqidan yutqazuvchi cho‘qqiga olib boradigan chiqish qirrasi bo‘lsa, u holda cho‘qqining o‘zi yutuvchi cho‘qqidir.
agar ma’lum bir cho‘qqining barcha chiqish qirralari yutuvchi cho‘qqilarga olib borsa, u holda cho‘qqining o‘zi yutqazuvchi cho‘qqidir.
agar bir paytda hali ham aniqlanmagan cho‘qqilar qolsa va ularning hech biri birinchi yoki ikkinchi qoidaga mos kelmasa, unda bu cho‘qqilarning har biri boshlang‘ich cho‘qqi sifatida ishlatilganda, agar ikkala o‘yinchi ham optimal o‘ynasa, durangga olib keladi.

Shunday qilib, darhol vaqt ichida ishlaydigan algoritmni aniqlashimiz mumkin. Biz barcha cho‘qqilarni ko‘rib chiqamiz va birinchi yoki ikkinchi qoidani qo‘llashga harakat qilamiz va takrorlaymiz.