Чип-игра - Chip-firing game

Пример графика
Возможная последовательность стрельбы с переменными состояния s(v) красным, а вершина, которая будет запущена, - желтым.

В игра-стрелялка однопользовательский игра на график который был изобретен примерно в 1983 году и с тех пор стал важной частью изучения структурная комбинаторика.

Определение

Пусть конечное график G быть связаны и без петель, с вершинами V = {1, 2, . . . , п}. Пусть deg (v) быть степень вершины, а e (v, w) количество ребер между вершинами v и ш. Конфигурация или состояние игры определяется присвоением каждой вершине неотрицательного целого числа s(v), представляющий количество фишек в этой вершине. Ход начинается с выбора вершины ш который имеет как минимум столько же фишек, сколько его степень: s(ш) ≥ deg (ш). Вершина ш является уволенный, перемещая одну микросхему от w вдоль каждого инцидентного ребра к соседней вершине, создавая новую конфигурацию определяется:

и для v ≠ w,

Состояние, в котором дальнейшая стрельба невозможна, называется стабильное состояние. Начиная с начальной конфигурации, игра продолжается со следующими результатами.

  • Если количество фишек меньше количества ребер, игра всегда конечна, достигая стабильного состояния.
  • Если в каждой вершине меньше фишек, чем ее степень, игра конечна.
  • Если количество фишек равно количеству ребер, игра может быть бесконечной, никогда не достигая стабильного состояния, для правильно выбранной начальной конфигурации.
  • Если количество фишек более чем в два раза превышает количество ребер минус количество вершин, игра всегда бесконечна.

Вариант Биггса

В варианте формы стружки, тесно связанной с модель кучи, также известный как долларовая игра, единственная особая вершина q обозначается как банк, и разрешено залезть в долги, приняв отрицательное целое значение s(q) <0. Если любая другая вершина может стрелять, банк не может стрелять, только собирает фишки. В итоге, q накопит столько фишек, что никакая другая вершина не сможет сработать: только в таком состоянии вершина q может стрелять фишками в соседние вершины, чтобы "запустить экономику".

Набор состояний, которые являются стабильными (т.е. для которых только q может стрелять) и повторяющиеся для этой игры могут иметь структуру абелева группа которое изоморфно прямому произведению и песчаная группа (также называемая группой Якоби или критической группой). Порядок последних - это дерево номер графа.[1][2]

Смотрите также

Рекомендации

  1. ^ Биггс, Норман Л. (25 июня 1997 г.). "Запуск микросхем и критическая группа графа" (PDF). Журнал алгебраической комбинаторики: 25–45. Получено 10 мая 2014.
  2. ^ викидот. "Ссылки на чип-обжиг". Получено 19 мая 2014.
  • А. Бьёрнер, Л. Ловас, П. В. Шор: Игры с запуском чипа на графах. Архив Европейского журнала комбинаторики, том 12, выпуск 4, июль 1991 г., страницы 283–291 Дои:10.1016 / S0195-6698 (13) 80111-4 PDF
  • А. Бьёрнер, Л. Ловас: Игры с запуском чипов на ориентированных графах. Журнал алгебраической комбинаторики, декабрь 1992 г., том 1, выпуск 4, стр. 305–328. Дои:10.1023 / А: 1022467132614

внешняя ссылка