Гра на графі

Матеріал з Вікіпедії — вільної енциклопедії.

Гра на графі — гра, представлена в наступному вигляді.

Даний граф Бержа L = (X, Γ) з виділеною підмножиною «початкових» вершин. Один із гравців (який саме, визначається жеребкуванням), в якості свого кроку обирає деяку вершину x₁ ∈ X₀; потім робить крок другий гравець, обираючи вершину y₁ ∈ Γx₁; після цього перший гравець обирає вершину x₂∈ Γy₁, і так далі. В багатьох іграх, переможцем вважається той, хто першим обере тупикову вершину — таку z, що Γz = ∅ (тобто, супротивника позбавлено можливості зробити наступний крок).

Гравець, який обрав в деякий момент часу вершину в ядрі — такому S ⊆ X, для якого ∀ x ∈ S Γx ∩ S = ∅ та ∀ x ∈ X \ S Γ x ∩ S ≠ ∅, має можливість, не залежно від відповіді противника, наступним своїм кроком знову обрати вершину в S, і так далі, тобто, застрахувати себе від програшу.

Також можуть існувати інші стратегії безпрограшної гри (навіть на графі, який не має жодного ядра).

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

[ред.] Джерела інформації

• Енциклопедія кібернетики, Зиков А. А., т. 1, с. 337-338.

[ред.] Дивіться також

• Теорія ігор

	Статті теорії ігор
Типи ігор	антагоністичні · диференціальні · матричні · на виживання · рефлексивні · азартні · без побічних платежів · безкоаліційні · біматричні · вироджені · динамічні · з вибором моменту часу · кооперативні · на графі · на одиничному квадраті · опуклі · позиційні · прості · рекурсивні · стохастичні
Ситуації	Безвиграшна ситуація · Парадокс Бертрана (економіка) · Ситуація рівноваги
Стратегія	змішана · оптимальна · поведінки · чиста
Теореми	Максіміна принцип · Мінімаксу теорема
Ігри	Дилема в'язня