Игра с фишками на графе — это , которая играется на графе с фишками (нуль и более фишек в вершинах). Игра заключается в серии ходов фишек, ход состоит в выборе вершины с двумя и более фишками, удалении их из вершины и добавлении одной фишки в смежную вершину (вторая удалённая фишка выбывает из игры). Фишечное число π(G) графа G — это наименьшее натуральное число n, удовлетворяющее следующим условиям: Для любой заданной целевой или «корневой» вершины в графе и любой начальной расстановки n фишек на графе после серии ходов (возможно, пустой), достичь новой конфигурации, в которой в выбранной корневой вершины будет одна или несколько фишек.
Например, в графе с 2 вершинами и 1 ребром, соединяющем эти вершины, фишечное число равно 2. Не имеет значения, в каких вершинах размещены эти фишки, всегда можно получить нужный результат, выбрав для хода вершину с фишками. Если в начальной конфигурации в обоих вершинах находится по фишке, то цель достигнута без всяких ходов. Одним из центральных вопросов игры с фишками на графе является величина π(G) для заданного графа G.
Другие темы игре с фишками включают «cover pebbling» (накрытие фишками), «optimal pebbling» (оптимальная игра с фишками), «domination cover pebbling» (доминирующее покрытие фишками), границы и пороги для фишечного числа, а также глубокие графы.
Одно из применений игр с фишками заключается в анализе безопасности в криптографии.
π(G) — фишечное число графа Игру с фишками впервые предложили Лагариас и Сакс как средство решения конкретной задачи в теории чисел. В 1989 году Фан Чун ввела это понятие в литературу и определила фишечное число π(G).
Легко проверить, что фишечное число полного графа с n вершинами равно n: Если у нас есть фишек, то мы можем положить по одной фишке в каждую вершину, кроме целевой. Так как не будет вершин с двумя или более фишками, нет возможности совершить ход, так что невозможно поместить фишку в целевую вершину. Таким образом, фишечное число должно быть больше . Если имеется n фишек, возможны два случая. Если каждая вершина содержит одну фишку, не требуется делать ходов. Если какая-либо вершина пуста, по меньшей мере одна другая вершина имеет две фишки на ней и один ход позволяет поместить в полном графе фишку в целевую вершину.
π(G) для семейств графов Фишечное число известно для следующих семейств графов: , где — полный граф с n вершинами. , где — путь с n вершинами. , где — колесо с n вершинами.
Фишечная гипотеза Грэма
Чун приписывает Рональду Грэму гипотезу, что фишечное число прямого произведения графов не больше произведения фишечных чисел сомножителейСмотрите статью Чан, вопрос 3 на странице 472.. Гипотеза стала известной как фишечная гипотеза Грэма. Гипотеза остаётся нерешённой, хотя некоторые специальные случаи известны.
γ(G) — число фишечного покрытия графа Крулл и др. ввели концепцию «фишечное покрытие». Число γ(G) фишечного покрытия графа G — это минимальное число фишек, необходимых, чтобы из любого начального распределения фишек после серии ходов граф был покрыт как минимум одной фишкой в каждой вершине.. Результат, называемый «stacking theorem» находит число фишечного покрытия для любого графа.
Stacking theorem Согласно теореме начальное расположение фишек, требующее максимального числа фишек для покрытия, случается при помещении всех фишек в одну вершину. Основываясь на этом, определим
для любой вершины v из G, где d(u,v) означает расстояние от u до v. Тогда число фишечного покрытия — это наибольшее s(v) для графа.
γ(G) для семейств графов Число фишечного покрытия известно для следующих семейств графов: , где — полный граф с n мершинами. , где — путь с n вершинами. , где — колесо с n вершинами.
Смотрите также Фишечная игра Proof-of-space
Примечания
Литература для даьнейшего чтения
Категория:Инварианты графов