График гальки - Graph pebbling - Wikipedia

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

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

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

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

π (грамм) - номер галочки графа

Игра в гальку была впервые предложена Лагариасом и Саксом в качестве инструмента для решения конкретной проблемы в теория чисел. В 1989 г. F.R.K. Чанг представил концепцию в литературе^[1] и определили число гальки π (грамм).

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

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

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

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

Гипотеза Грэхема

Нерешенная проблема в математике: Является ли число камней декартова произведения графов не более чем произведением количества камней графов? (больше нерешенных задач по математике)

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

γ (грамм) - номер покрытия графа

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

Теорема о стеке

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

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

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

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

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

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

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

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

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

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