Граф камушка

Камушка графа — это математическая игра, в которую играют на графе , в каждой вершине которого имеется ноль или более камешков . «Игра» состоит из серии камешковых ходов. Ход камешка на графе состоит из выбора вершины, в которой есть хотя бы два камешка, удаления из нее двух камушков и добавления одного в соседнюю вершину (второй удаленный камешек выбрасывается из игры). π( G ), число камня графа G , является наименьшим натуральным числом n, которое удовлетворяет следующему условию:

Учитывая любую целевую или «корневую» вершину в графе и любую начальную конфигурацию из n камешков на графе, после возможно пустой серии ходов камешков можно достичь новой конфигурации, в которой назначенная корневая вершина имеет один или больше камешков.

Например, в графе с 2 вершинами и 1 соединяющим их ребром число камешков равно 2. Независимо от того, как два камешка расположены в вершинах графа, всегда можно прийти к желаемому результату, когда выбранная вершина имеет галька; если исходная конфигурация представляет собой конфигурацию с одним камешком на вершину, то цель тривиально достигается с нулевым движением камешков. Одним из центральных вопросов разметки графов является значение π( G ) для данного G. графа

Другие темы гальки включают гальку покрытия, оптимальную гальку, гальку доминирования покрытия, границы и пороги для чисел гальки, а также глубокие графики.

Одним из применений игр с пеблингом является анализ безопасности функций с жесткой памятью в криптографии .

π( G ) — число камня графа

Игра в камешки была впервые предложена Лагариасом и Саксом как инструмент для решения конкретной задачи теории чисел . В 1989 году ФРК Чунг представил эту концепцию в литературе. и определил число гальки π( G ).

Число камешков для полного графа с n вершинами, как легко проверить, равно n : если бы у нас было ( n − 1) камешков, которые нужно было положить в граф, то мы могли бы положить по одному камню в каждую вершину, кроме цели. Поскольку ни в одной вершине нет двух или более камешков, ходы невозможны, поэтому невозможно поместить камешек в цель. Таким образом, число камешков должно быть больше n - 1. Учитывая n камешков, возможны два случая. Если в каждой вершине находится один камешек, ходов не требуется. Если какая-либо вершина пуста, по крайней мере в одной другой вершине должно быть два камешка, а одно движение камешка позволяет добавить камешек в любую целевую вершину полного графа.

π( G ) для семейств графов

Число камешка известно для следующих семейств графов:

• $\pi (K_{n})\,=\,n$, где $K_{n}$ является полным графом на n вершинах.
• $\pi (P_{n})\,=\,2^{n-1}$, где $P_{n}$ представляет собой граф путей на n вершинах.
• $\pi (W_{n})\,=\,n$, где $W_{n}$ представляет собой граф-колесо на n вершинах.

Грэма

Нерешенная задача по математике :

Является ли число качки декартова произведения графов не более чем произведением числа качки графов?

(еще нерешенные задачи по математике)

Чанг (1989) приписал Рональду Грэму гипотезу о том, что число дробления декартова произведения графов не более чем равно произведению чисел дробления факторов в продукте. Это стало известно как гипотеза Грэма о камне . Она остается нерешенной, хотя известны частные случаи.

γ( G ) — число покрытия графа

Крулл и др. представил концепцию покровной гальки. γ( G ), число покрывающих камешков графа — это минимальное количество камешков, необходимое для того, чтобы из любого начального расположения камешков после серии ходов камешков граф был покрыт: в каждой вершине находился хотя бы один камешек . Результат, называемый теоремой наложения, позволяет найти число покрытия для любого графа.

Теорема о суммировании

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

$s(v)=\sum _{u\in V(G)}2^{d(u,v)}$

для каждой вершины v в G , где d ( u , v ) обозначает расстояние от u до v . Тогда число камешков на покрытии будет наибольшим s ( v полученным ).

γ( G ) для семейств графов

Число покрытия покрытий известно для следующих семейств графов:

• $\gamma (K_{n})\,=\,2n-1$, где $K_{n}$ является полным графом на n вершинах.
• $\gamma (P_{n})\,=\,2^{n}-1$, где $P_{n}$ путь n на вершинах .
• $\gamma (W_{n})\,=\,4n-9$, где $W_{n}$ представляет собой граф-колесо на n вершинах.

См. также

• Игра с камушками
• Доказательство пространства

Дальнейшее чтение

• Чан, Мелоди ; Годболе, Анант П. (2008). «Улучшенные границы гальки». Дискретная математика . 308 (11): 2301–2306. arXiv : math/0510045 . дои : 10.1016/j.disc.2006.06.032 . МР   2404560 . S2CID   5501949 .
• Херлберт, Гленн Х. (1999). «Обзор графической гальки» (PDF) . Материалы тридцатой Юго-восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1999) . Конгресс Нумерантиум. Том. 139. стр. 41–64. МР   1744229 .
• Пахтер, Лиор ; Сневили, Хантер С.; Воксман, Билл (1995). «О галечных графах» (PDF) . Материалы двадцать шестой Юго-восточной международной конференции по комбинаторике, теории графов и информатике (Бока-Ратон, Флорида, 1995) . Конгресс Нумерантиум. Том. 107. С. 65–80. МР   1369255 . Архивировано из оригинала (PDF) 25 ноября 2015 г.