DOI: https://doi.org/10.32626/2308-5878.2018-18.100-105

Комбінаторна гра — «Зв’язна незв’язність»

Сергій Олександрович Кріль, Марк Михайлович Зегельман

Анотація


Комбінаторна теорія ігор — це математична теорія, що вивчає ігри двох осіб, де у кожен момент часу є позиція, яку гравці почергово змінюють певним чином, щоб досягти певного виграшу. Комбінаторні ігри можуть бути інтерпретовані як ігри на графах.

У роботі розглядається комбінаторна гра на неорієнтованому графі «Зв’язна незв’язність», яка може бути використаною при моделюванні процесів конкурентної боротьби. Для розв’язання цієї задачі розроблено власний метод фінальних графів, який полягає в аналізі ситуації, яка утворилась за крок до завершення гри. В роботі доводиться оптимальність стратегії, результатом якої є повне розв’язання задачі для довільної кількості вершин. При дослідженні гри встановлено переможця в залежності від остачі, яку дає кількість вершин при діленні на чотири.

Актуальність теми визначається надзвичайно широким спектром застосування теорії графів при моделюванні різних процесів підприємницької діяльності, тощо. Комбінаторна теорія ігор на графах може бути застосована в задачах кластеризації, а також при моделюванні конфліктних ситуацій. Відмінність комбінаторних ігор від ігор, які зазвичай вивчаються в класичній («економічній») теорії ігор полягає в тому, що в них гравці виконують ходи по черзі, а не одночасно (класична теорія ігор висвітлюється в безлічі книг, у назві яких фігурують слова «теорія ігор» або «дослідження операцій»).

Міркування комбінаторної теорії ігор з повною інформацією з'явилися, ще в давні часи, наприклад в книзі Сунь Цзи «Мистецтво війни»: якщо можна прорахувати, кому дістанеться перемога, а власне саму війну не затівати.

Ця стаття може бути корисною усім, хто цікавиться комбінаторною теорією ігор, теорією графів. Результати даного дослідження мають різне прикладне застосування. Тема є перспективною для подальшого продовження роботи в цьому напрямку.

Повний текст:

PDF

Посилання


Деорнуа П. Комбинаторная теория игр / П. Деорнуа. — М. : Издательство МЦНМО, 2017. — 40 с.

Шиян А. А. Теорія ігор: основи та застосування в економіці та менеджменті : навч. посіб. / А. А. Шиян. — Вінниця : ВНТУ, 2009. — 164 с.

Aaron NSiegel. Combinatorial Game Theory / AaronNSiegel // American Math-ematical Society, 2013. — 525 p.

Спекторський І. Я. Дискретна математика. Збірник задач / І. Я. Спекторський, О. В. Стусь, В. М. Статкевич. — К. : НТУУ «КПІ», 2015. — С. 35–38.

Трохимчук Р. М. Теорія графів. Навчальний посібник для студентів факу-льтету кібернетики / Р. М. Трохимчук. — К. : РВЦ «Київський універси-тет», 1998. — 43 с.