Комбінаторна гра — "Зв'язна незв'язність"
Комбінаторна теорія ігор — це математична теорія, що вивчає ігри двох осіб, де у кожен момент часу є позиція, яку гравці почергово змінюють певним чином, щоб досягти певного виграшу. Комбінаторні ігри можуть бути інтерпретовані як ігри на графах. У роботі розглядається комбінаторна гра на неорієнтов...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Schriftenreihe: | Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/162222 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Комбінаторна гра — "Зв'язна незв'язність" / С.О. Кріль, М.М. Зегельман // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2018. — Вип. 18. — С. 100-105. — Бібліогр.: 5 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-162222 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1622222020-01-05T01:25:27Z Комбінаторна гра — "Зв'язна незв'язність" Кріль, С.О. Зегельман, М.М. Комбінаторна теорія ігор — це математична теорія, що вивчає ігри двох осіб, де у кожен момент часу є позиція, яку гравці почергово змінюють певним чином, щоб досягти певного виграшу. Комбінаторні ігри можуть бути інтерпретовані як ігри на графах. У роботі розглядається комбінаторна гра на неорієнтованому графі «Зв’язна незв’язність», яка може бути використаною при моделюванні процесів конкурентної боротьби. Для розв’язання цієї задачі розроблено власний метод фінальних графів, який полягає в аналізі ситуації, яка утворилась за крок до завершення гри. В роботі доводиться оптимальність стратегії, результатом якої є повне розв’язання задачі для довільної кількості вершин. При дослідженні гри встановлено переможця в залежності від остачі, яку дає кількість вершин при діленні на чотири. The combinatorial theory of games is a mathematical theory that examines the games of two persons, where at each moment of time there is a position that players in turn change in a certain way in order to achieve a certain gain. Combination games can be interpreted as games on graphs. In this paper we consider a combinatorial game on a non-oriented graph «Connective incompatibility», which can be used in the simulation of competitive struggle. To solve this problem, an own method of final graphs has been developed, which consists in analyzing the situation that was formed one step before the end of the game. The optimality of the strategy, which results in the complete solution of the problem for an arbitrary number of vertices, is presented in the paper. In the study of the game set the winner, depending on the remainder, this gives the number of vertices when dividing by four. 2018 Article Комбінаторна гра — "Зв'язна незв'язність" / С.О. Кріль, М.М. Зегельман // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2018. — Вип. 18. — С. 100-105. — Бібліогр.: 5 назв. — укр. DOI: 10.32626/2308-5878.2018-18.100-10 2308-5878 http://dspace.nbuv.gov.ua/handle/123456789/162222 519.1 uk Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Комбінаторна теорія ігор — це математична теорія, що вивчає ігри двох осіб, де у кожен момент часу є позиція, яку гравці почергово змінюють певним чином, щоб досягти певного виграшу. Комбінаторні ігри можуть бути інтерпретовані як ігри на графах. У роботі розглядається комбінаторна гра на неорієнтованому графі «Зв’язна незв’язність», яка може бути використаною при моделюванні процесів конкурентної боротьби. Для розв’язання цієї задачі розроблено власний метод фінальних графів, який полягає в аналізі ситуації, яка утворилась за крок до завершення гри. В роботі доводиться оптимальність стратегії, результатом якої є повне розв’язання задачі для довільної кількості вершин. При дослідженні гри встановлено переможця в залежності від остачі, яку дає кількість вершин при діленні на чотири. |
| format |
Article |
| author |
Кріль, С.О. Зегельман, М.М. |
| spellingShingle |
Кріль, С.О. Зегельман, М.М. Комбінаторна гра — "Зв'язна незв'язність" Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| author_facet |
Кріль, С.О. Зегельман, М.М. |
| author_sort |
Кріль, С.О. |
| title |
Комбінаторна гра — "Зв'язна незв'язність" |
| title_short |
Комбінаторна гра — "Зв'язна незв'язність" |
| title_full |
Комбінаторна гра — "Зв'язна незв'язність" |
| title_fullStr |
Комбінаторна гра — "Зв'язна незв'язність" |
| title_full_unstemmed |
Комбінаторна гра — "Зв'язна незв'язність" |
| title_sort |
комбінаторна гра — "зв'язна незв'язність" |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2018 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/162222 |
| citation_txt |
Комбінаторна гра — "Зв'язна незв'язність" / С.О. Кріль, М.М. Зегельман // Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки: зб. наук. пр. — Кам’янець-Подільський: Кам'янець-Подільськ. нац. ун-т, 2018. — Вип. 18. — С. 100-105. — Бібліогр.: 5 назв. — укр. |
| series |
Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки |
| work_keys_str_mv |
AT krílʹso kombínatornagrazvâznanezvâznístʹ AT zegelʹmanmm kombínatornagrazvâznanezvâznístʹ |
| first_indexed |
2025-07-14T14:44:52Z |
| last_indexed |
2025-07-14T14:44:52Z |
| _version_ |
1837633941766406144 |
| fulltext |
Математичне та комп’ютерне моделювання
100
УДК 519.1
DOI: 10.32626/2308-5878.2018-18.100-105
С. О. Кріль*, канд. фіз.-мат. наук,
М. М. Зегельман**
* Кам'янець-Подільський національний університет
імені Івана Огієнка, м. Кам'янець-Подільський,
** Кам'янець-Подільський ліцей, м. Кам'янець-Подільський
КОМБІНАТОРНА ГРА — «ЗВ’ЯЗНА НЕЗВ’ЯЗНІСТЬ»
Комбінаторна теорія ігор — це математична теорія, що вивчає
ігри двох осіб, де у кожен момент часу є позиція, яку гравці поче-
ргово змінюють певним чином, щоб досягти певного виграшу.
Комбінаторні ігри можуть бути інтерпретовані як ігри на графах.
У роботі розглядається комбінаторна гра на неорієнтованому
графі «Зв’язна незв’язність», яка може бути використаною при
моделюванні процесів конкурентної боротьби. Для розв’язання
цієї задачі розроблено власний метод фінальних графів, який по-
лягає в аналізі ситуації, яка утворилась за крок до завершення гри.
В роботі доводиться оптимальність стратегії, результатом якої є
повне розв’язання задачі для довільної кількості вершин. При до-
слідженні гри встановлено переможця в залежності від остачі, яку
дає кількість вершин при діленні на чотири.
Актуальність теми визначається надзвичайно широким
спектром застосування теорії графів при моделюванні різних
процесів підприємницької діяльності, тощо. Комбінаторна те-
орія ігор на графах може бути застосована в задачах кластери-
зації, а також при моделюванні конфліктних ситуацій. Відмін-
ність комбінаторних ігор від ігор, які зазвичай вивчаються в
класичній («економічній») теорії ігор полягає в тому, що в них
гравці виконують ходи по черзі, а не одночасно (класична тео-
рія ігор висвітлюється в безлічі книг, у назві яких фігурують
слова «теорія ігор» або «дослідження операцій»).
Міркування комбінаторної теорії ігор з повною інформаці-
єю з'явилися, ще в давні часи, наприклад в книзі Сунь Цзи
«Мистецтво війни»: якщо можна прорахувати, кому дістанеть-
ся перемога, а власне саму війну не затівати.
Ця стаття може бути корисною усім, хто цікавиться комбі-
наторною теорією ігор, теорією графів. Результати даного дос-
лідження мають різне прикладне застосування. Тема є перспек-
тивною для подальшого продовження роботи в цьому напрямку.
Ключові слова: комбінаторна теорія ігор, теорія графів,
метод фінальних графів, комбінаторні ігри на графах.
Вступ. Комбінаторні ігри можуть бути інтерпретовані як ігри на
графах [1]. Теорія ігор розглядає моделювання ринкової економіки,
© С. О. Кріль, М. М. Зегельман, 2018
Серія: Фізико-математичні науки. Випуск 18
101
прийняття рішень в умовах жорсткої конкурентної боротьби [2].
Комбінаторні ігри розглядались в [3].
Означення 1. Графом називається така впорядкована пара мно-
жин G = (V, E), де V — множина вершин, а E — множина ребер, під-
множина V × V [4, с. 35].
Означення 2. Двочастковим графом називається граф, множина
вершин якого може бути розбита на дві підмножини так, що кожне ребро
графа має одну вершину з першої підмножини і одну з другої [5, с. 25].
Означення 3. Зв'язний граф — граф що містить рівно одну ком-
поненту зв'язності [5, с. 11].
Означення 4. Компонента зв'язності — це підграф, в якому
будь-які дві вершини зв'язані одна з одною шляхами, і вони не зв'яза-
ні з ніякими додатковими вершинами [5, с. 13].
Означення 5. Нехай граф G, який утворився під час гри, такий,
що додавання до нього будь-якого ребра приводить до програшу.
Назвемо такий граф G — фінальним.
Основна частина. Розглянемо ситуацію, яка могла скластися в
стародавньому Римі. Є два претенденти стати імператором та n трибу-
нів, (посада в стародавньому Римі) які не дружать. Два претендента по
черзі вибирають пару трибунів, які не дружать та роблять їх друзями.
Претендент, який зробив таку ситуацію, всі трибуни дружать (можливо
через інших друзів) програє, а інший претендент стає імператором.
Розглянемо математичну модель цієї задач у термінах графів.
Задача «Зв’язна незв’язність». Два гравці по черзі додають ре-
бра до неорієнтованого графа, який на початку гри порожній та міс-
тить n вершин, n ≥ 5. Гравець, який одержав зв'язний граф програв.
Хто виграє за правильної гри в залежності від n?
Теорема. Перший гравець виграє тоді і тільки тоді, коли
n = 4k + 2 або n = 4k + 3.
Доведення. Фінальний граф буде складатися з двох компонент
зв'язності, кожна з яких є повним підграфом. Оскільки при додаванні
до графа ребер кількість компонент зв'язності може зменшитися або
залишитися сталою, тому коли залишиться дві компоненти зв'язності
гравці, щоб запобігти програшу будуть додавати ребра всередині ко-
жної компоненти. Після того як кожна компонента стане повним під-
графом додавання кожного ребра призводитиме до програшу, тому
одержаний граф є фінальним. Зауважимо, що якщо компоненти зв'яз-
ності складаються з m та k вершин, то фінальний граф містить
2 2 ( 1) ( 1)
2m k
m m k kC C
ребер. Коли це число парне, то виграє
Математичне та комп’ютерне моделювання
102
другий гравець, а якщо не парне, то перший. Зрозуміло, що під час
гри важлива кількість компонент зв'язності, кількість ребер в кожній
компоненті та неважливо, які саме вершини з'єднані в компонентах
зв'язності. Позначимо Gm, k — граф, який містить дві компоненти зв'я-
зності, які складаються m та k вершин.
Лема 1. Графи Gn – 2z, 2z є виграшними для першого гравця при
n = 4k + 2 та n = 4k + 3, а для другого при n = 4k та n = 4k + 1.
Доведення. Граф Gn – 2z, 2z може містити не більше ніж
2 2
2 2
( 2 )( 2 1) 2 (2 1)
2n z z
n z n z z zC C
.
Підставимо n = 4k та отримаємо:
2 2
4 2 2
2 2
(4 2 )(4 1 2 ) 2 (2 1)
2
(2 )(4 2 1) (2 1) 8 2 8 4
k z z
k z k z z zC C
k z k z z z k k kz z
— парне.
Аналогічно при n = 4k + 1:
2 2
4 1 2 2
2 2
(4 1 2 )(4 2 ) 2 (2 1)
2
(4 1 2 )(2 ) (2 1) 8 2 8 4 2
k z z
k z k z z zC C
k z k z z z k k kz z z
–парне.
При n = 4k + 2:
2 2
4 2 2 2
2 2
(4 2 2 )(4 1 2 ) 2 (2 1)
2
(2 1 )(4 1 2 ) (2 1) 8 6 8 4 4 1
k z z
k z k z z zC C
k z k z z z k k kz z z
— непарне.
При n = 4k + 3:
2 2
4 3 2 2
2 2
(4 3 2 )(4 2 2 ) 2 (2 1)
2
(4 3 2 )(2 1 ) (2 1) 8 10 8 4 6 3
k z z
k z k z z zC C
k z k z z z k k kz z z
— непарне.
Отже при n = 4k + 2 та n = 4k + 3 виграє перший гравець, а при
n = 4k та n = 4k + 1 — другий. Лема 1 доведена.
Відомо, що зв'язний граф з k вершинами містить не менше ніж
k – 1 ребро, назвемо k – 1 ребро (які утворюють дерево) основними, а
інші ребра допоміжними.
Компоненти зв'язності, які не містять ребра, тобто складаються
лише з однієї ізольованої вершини будемо називати порожньою.
Лема 2. Граф, який містить n = 4k + 1 вершину завжди є вигра-
шним для другого гравця, а граф який містить n = 4k + 3 вершину
завжди є виграшним для першого гравця (за будь-якої гри).
Серія: Фізико-математичні науки. Випуск 18
103
Доведення. Нехай в грі ми отримали фінальний граф Gm, p, оскі-
льки m + p = 4k + 1, то одне з чисел m або p — парне (якщо припус-
тити, що m та p непарні, то їхня сума буде парною, отримали проти-
річчя). Отже одна з компонент зв'язності фінального графа складаєть-
ся з парної кількості вершин, тому за лемою 1 при n = 4k + 1 виграє
другий гравець, а при n = 4k + 3 — перший. Лема 2 доведена.
Лема 3. Граф, який містить n = 4k вершин є виграшним для дру-
гого гравця.
Доведення. Для цього другий гравець об'єднує дві компоненти
зв'язності, які мають найбільшу кількість вершин до моменту коли в
компоненті буде n – 4 або n – 3 вершини. Другий гравець завжди цьо-
го зможе досягти, оскільки при таких діях в графі — не більше двох
не порожніх компонент зв'язності, менша з яких складається не біль-
ше ніж з двох вершин. Тому при об'єднанні двох компонент зв'язнос-
ті кількість вершин у найбільшій компоненті збільшується на один
або на два. Оскільки n – 4 та n – 3 два натуральних числа підряд то
після ходу другого гравця найбільша компонента зв'язності буде
складатися з n – 4 або n – 3 вершин. Розглянемо два варіанта.
Варіант 1. Після ходу другого гравця утворився граф Gn – 4,1,1,1,1.
Перший гравець може перейти в граф Gn – 3,1,1,1, тоді другий гра-
вець передає хід (додає допоміжні ребра всередині компоненти
зв’язності). Він завжди зможе це зробити, оскільки максимальна кі-
лькість допоміжних ребер складає: ( 3)( 4) 2( 4)
2
n n n — парне,
оскільки n = 4k. В ситуації Gn – 3, 1, 1, 1 другий гравець може передати
хід, оскільки перед його ходом кількість допоміжних ребер, які мож-
на додати, є непарною (всього допоміжних ребер — парна кількість, а
вже додано непарну кількість).Також перший гравець може перейти в
граф Gn – 4, 2, 1, 1. Тоді другий гравець Gn – 4, 2, 2, після цього перший гра-
вець може утворити фінальні графи Gn – 4, 4 або Gn – 2, 2 та за лемою 1
програє. Перший гравець може перейти в граф Gn – 4, 1, 1, 1, 1 (додавши
допоміжні ребра в найбільшій компоненті), тоді другий гравець пере-
ходить в граф Gn – 3, 1, 1, 1 (розглядається в варіанті 2).
Варіант 2. Після ходу другого гравця утворився граф. Gn – 3, 1, 1, 1.
Перший гравець може перейти в граф Gn – 2, 1, 1. Тоді другий гра-
вець переходить в граф Gn – 2, 2 та за лемою 1 виграє. Перший гравець
може перейти в граф Gn – 3, 2. Тоді другий гравець переходить в граф
Gn – 2, 2 та за лемою 1 виграє. Зауважимо, що перший гравець в графі
Gn – 3, 1, 1, 1 не може передати хід, оскільки в найбільшій компоненті
зв'язності (всього допоміжних ребер — парна кількість, а вже додано
парну кількість). Лема 3 доведена.
Математичне та комп’ютерне моделювання
104
Лема 4. Граф, який містить n = 4k + 2 вершин є виграшним для
першого гравця.
Доведення. Для цього перший гравець грає за алгоритмом гри
описаним в лемі 3 для другого гравця. Тобто він збільшує найбільшу
компоненту зв'язності до n – 3 або n – 4. Зауважимо, що в графі
Gn – 3, 1, 1, 1 перший гравець може передати хід (додавши допоміжні
ребра всередині компоненти зв’язності, оскільки максимальна кіль-
кість допоміжних ребер складає: ( 3)( 4) 2( 4)
2
n n n — непарне,
оскільки n = 4k + 2. Перед його ходом кількість допоміжних ребер,
які можна додати, є непарною (всього допоміжних ребер — непарна
кількість, а вже додано парну кількість). Лема 4 доведена.
З лем 2–4 випливає правильність теореми. Теорема доведена.
Висновки: комбінаторна гра «Зв’язна незв’язність» є моделю-
ванням процесів конкурентної боротьби двох сторін. При дослі-
дженні гри встановлено:
1) при n = 4k за правильної гри виграє другий гравець;
2) при n = 4k + 1 за будь-якої гри виграє другий гравець;
3) при n = 4k + 2 за правильної гри виграє перший гравець;
4) при n = 4k + 3 за будь-якої гри виграє перший гравець.
Список використаних джерел:
1. Деорнуа П. Комбинаторная теория игр / П. Деорнуа. — М. : Издательство
МЦНМО, 2017. — 40 с.
2. Шиян А. А. Теорія ігор: основи та застосування в економіці та менедж-
менті : навч. посіб. / А. А. Шиян. — Вінниця : ВНТУ, 2009. — 164 с.
3. Aaron NSiegel. Combinatorial Game Theory / AaronNSiegel // American
Mathematical Society, 2013. — 525 p.
4. Спекторський І. Я. Дискретна математика. Збірник задач / І. Я. Спекторський,
О. В. Стусь, В. М. Статкевич. — К. : НТУУ «КПІ», 2015. — С. 35–38.
5. Трохимчук Р. М. Теорія графів. Навчальний посібник для студентів фа-
культету кібернетики / Р. М. Трохимчук. — К. : РВЦ «Київський універ-
ситет», 1998. — 43 с.
COMBINATORIAL GAME —
«CONNECTIVE INCOMPATIBILITY»
The combinatorial theory of games is a mathematical theory that exam-
ines the games of two persons, where at each moment of time there is a po-
sition that players in turn change in a certain way in order to achieve a cer-
tain gain. Combination games can be interpreted as games on graphs.
In this paper we consider a combinatorial game on a non-oriented graph
«Connective incompatibility», which can be used in the simulation of competi-
tive struggle. To solve this problem, an own method of final graphs has been
developed, which consists in analyzing the situation that was formed one step
before the end of the game. The optimality of the strategy, which results in the
Серія: Фізико-математичні науки. Випуск 18
105
complete solution of the problem for an arbitrary number of vertices, is pre-
sented in the paper. In the study of the game set the winner, depending on the
remainder, this gives the number of vertices when dividing by four.
The urgency of this topic is determined by an extremely wide spectrum of
the theory of graphs in the modeling of various processes of entrepreneurial ac-
tivity, etc. The combinatorial theory of games on graphs can be applied in clus-
tering tasks, as well as in the simulation of conflict situations. The difference
between combinatorial games from games, which are usually studied in the
classical («economic») game theory, is that players play in turns in turn, and
not simultaneously (the classical game theory is covered in a multitude of
books, which include the words «theory games «or» research operations»).
Considerations of the combinatorial theory of games with full information
have appeared, even in ancient times, for example, in Sun Tzu's book «The Art
of War»: if one can calculate who will win, and not actually fight the war itself.
This article can be useful to anyone interested in the combinatorial theory of
games, graph theory. The results of this study have different application applica-
tions. The topic is promising for further continuation of work in this direction.
Key words: combinatorial game theory,graph theory,method of final
graphs, combinatorial games on graphs
Отримано: 23.11.2018
УДК 517.9
DOI: 10.32626/2308-5878.2018-18.105-112
В. А. Літовченко, д-р фіз.-мат. наук, професор
Чернівецький національний університет
імені Юрія Федьковича, м. Чернівці
ГЛАДКІ РОЗВ’ЯЗКИ ГІПЕРБОЛІЧНИХ ЗА ШИЛОВИМ СИСТЕМ
Для широкого класу гіперболічних за Шиловим лінійних сис-
тем рівнянь із частинними похідними, який охоплює клас Пет-
ровського гіперболічних систем зі сталими коефіцієнтами і міс-
тить клас рівнянь Гордінга, розглядається питання знаходження
гладких класичних розв’язків, які є стосовно просторової змінної
фінітними або швидко спадними на нескінченності вектор-
функціями. Дослідження проводяться методом перетворення
Фур’є у поєднанні з теорією просторів типу S i S’ Гельфанда І. М.
і Шилова Г. Є. основних і узагальнених функцій. Належність
компонент фундаментального розв’язку задачі Коші для таких
систем до простору розподілів Дірака, а також, їх згортковість у
певних просторорах типу S основних функцій дозволило тут
установити в класичному розумінні коректну розв’язність задачі
Коші в кожному такому просторі Гельфанда і Шилова. Тобто, до-
вести існування, єдиність та неперервну залежність від почат-
кових даних класичного розв’язку гіперболічної системи у зазна-
ченому просторі типу S, за умови, що його граничне значення на
© В. А. Літовченко, 2018
|