Комбінаторні ігри на графах

Abstract

Теорія ігор розглядає завдання, типові до ринкової економіки, прийняття рішень в умовах жорсткої конкурентної боротьби. Гра – це конфліктна ситуація, регламентована певними правилами, в яких мають бути вказані: порядок чергування дій учасників ходів; правила виконання кожного ходу; кількісний результат гри. Існує багато застосувань теорії ігор на графах в інших областях математики, а також у бізнесі, економіці, політиці, штучному інтелекті тощо. Наприклад, у бізнесі трапляються ситуації, схожі на математичні ігри, тому підприємці можуть використовувати знання теорії ігор для максимізації власного прибутку. Розглянуті у роботі ігри на графах мають різні інтерпретації та застосування, а саме: конкуренція двох провайдерів в одному місці; задача про визначення руху фанатів перед спортивною подією; конкуренцію двох засновників, що мають вплив в корпорації. Для кожної задачі знайдено стратегію та доведено її оптимальність. Мета дипломної роботи – створити власні ігри на графах та розробити виграшні стратегії, та довести їх оптимальність використовуючи теорію графів, та комбінаторні методи доведення.