Гра на графі

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

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

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

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

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

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

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

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


Статті теорії ігор

Типи ігор

антагоністичні · диференціальні · матричні · на виживання · рефлексивні · азартні · без побічних платежів · безкоаліційні · біматричні · вироджені · динамічні · з вибором моменту часу · кооперативні · на графі · на одиничному квадраті · опуклі · позиційні · прості · рекурсивні · стохастичні 

Ситуації

Безвиграшна ситуація · Парадокс Бертрана (економіка) · Ситуація рівноваги 

Стратегія

змішана · оптимальна · поведінки · чиста 

Теореми

Максіміна принцип · Мінімаксу теорема

Ігри

Дилема в'язня