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

Анотація

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

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

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

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

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