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

Пример графика

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

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

Определение

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

${\displaystyle s'(w)=s(w)-\deg(w)}$

и для v ≠ w,

${\displaystyle s'(v)=s(v)+e(v,w).}$

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

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

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

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

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

Набор состояний, которые являются стабильными (т.е. для которых только q может стрелять) и повторяющиеся для этой игры могут иметь структуру абелева группа которое изоморфно прямому произведению ${\displaystyle \mathbb {Z} }$ и песчаная группа (также называемая группой Якоби или критической группой). Порядок последних - это дерево номер графа.^[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

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

• Курс MIT 18.312: Алгебраическая комбинаторика
• Вайс Агостон: A koronglövő játék. Сзакдолгозат, ELTE TTK Bsc, 2014^{[постоянная мертвая ссылка ]}
• Исследование обжига чипов на Egerváry Research Group
• Игры, построенные на стрельбе из чипов (2010)
• Игра в доллар - Numberphile видео