График гальки

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

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

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

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

π ( G ) - число галечников графа [ править ]

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

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

π ( G ) для семейств графов [ править ]

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

• ${\ Displaystyle \ пи (К_ {п}) \, = \, п}$, где - полный граф на n вершинах. ^[1]${\ displaystyle K_ {n}}$
• ${\ Displaystyle \ пи (Р_ {п}) \, = \, 2 ^ {п-1}}$, где - граф путей на n вершинах. ^[1]${\ displaystyle P_ {n}}$
• ${\ Displaystyle \ пи (W_ {п}) \, = \, п}$, где - колесный граф на n вершинах.${\ displaystyle W_ {n}}$

Гипотеза Грэма [ править ]

Чанг (1989) приписал Рональду Грэхему гипотезу о том, что число отслаивания декартова произведения графов не более чем равно произведению числа отслаивания факторов в произведении. ^[2] Это стало известно как гипотеза Грэхема . По состоянию на 2019 год ^{[Обновить]}он остается нерешенным, хотя известны особые случаи. ^[3]

γ ( G ) - число покрывания графа [ править ]

Crull et al. ввела понятие покровной гальки. γ ( G ) покрывающее число камешков графа - это минимальное количество камешков, необходимое для того, чтобы при любом начальном расположении камешков после серии ходов камешков граф был покрыт: на каждой вершине есть хотя бы один камешек . ^[4] Результат, называемый теоремой о суммировании, находит число склеивания покрытия для любого графа. ^{[5] [6]}

Теорема о суммировании [ править ]

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

${\ Displaystyle s (v) = \ сумма _ {u \ in V (G)} 2 ^ {d (u, v)}}$

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

γ ( G ) для семейств графов [ править ]

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

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

См. Также [ править ]

• Галька игра
• Доказательство места

Ссылки [ править ]

Дальнейшее чтение [ править ]