Гра на графі

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

Дано граф Бержа 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.