Введение
Математическая игра, играемая на графе. Графическое окатывание (pebbling) – это математическая игра, играемая на графе с нулем или более окатышей на каждой из его вершин. Игровой процесс состоит из серии ходов окатывания. Ход окатывания на графе заключается в выборе вершины с по крайней мере двумя окатышами, удалении двух окатышей с неё и добавлении одного в смежную вершину (второй удалённый окатыш исключается из игры). π(G), число окатывания графа G, – это наименьшее натуральное число n, которое удовлетворяет следующему условию: для любой целевой или «корневой» вершины в графе и любой начальной конфигурации из n окатышей на графе возможно, после, возможно, пустой серии ходов окатывания, достичь новой конфигурации, в которой указанная корневая вершина имеет один или несколько окатышей. Например, для графа с 2 вершинами и 1 ребром, соединяющим их, число окатывания равно 2. Независимо от того, как расположены два окатыша на вершинах графа, всегда можно добиться желаемого результата – наличия окатыша на выбранной вершине; если начальная конфигурация – конфигурация с одним окатышем на вершину, то цель достигается тривиально без ходов окатывания. Один из центральных вопросов в задаче об окатывании графов – определение значения π(G) для заданного графа G. Другие темы, связанные с окатыванием, включают окатывание покрытием, оптимальное окатывание, окатывание покрытием доминирования, границы и пороговые значения для чисел окатывания, а также глубокие графы. Одно из применений игр окатывания – анализ безопасности функций, устойчивых к атакам по памяти, в криптографии.
Graph pebbling is a mathematical game played on a graph with zero or more pebbles on each of its vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of choosing a vertex with at least two pebbles, removing two pebbles from it, and adding one to an adjacent vertex (the second removed pebble is discarded from play). π(G), the pebbling number of a graph G, is the lowest natural number n that satisfies the following condition:
Given any target or 'root' vertex in the graph and any initial configuration of n pebbles on the graph, it is possible, after a possibly empty series of pebbling moves, to reach a new configuration in which the designated root vertex has one or more pebbles. For example, on a graph with 2 vertices and 1 edge connecting them the pebbling number is 2. No matter how the two pebbles are placed on the vertices of the graph it is always possible to arrive at the desired result of the chosen vertex having a pebble; if the initial configuration is the configuration with one pebble per vertex, then the objective is trivially accomplished with zero pebbling moves. One of the central questions of graph pebbling is the value of π(G) for a given graph G.
Other topics in pebbling include cover pebbling, optimal pebbling, domination cover pebbling, bounds, and thresholds for pebbling numbers, as well as deep graphs. One application of pebbling games is in the security analysis of memory hard functions in cryptography.
π ((G) число пебблирования графа
Игра в камешки была впервые предложена Лагариасом и Саксом как инструмент для решения конкретной задачи в теории чисел. В 1989 году Ф. Р. К. Чунг ввёл это понятие в научную литературу и определил число пебблинга, π(G). Число пебблинга для полного графа на n вершинах легко доказать равным n: если бы у нас было (n − 1) камешков для размещения на графе, мы могли бы разместить по одному камешку на каждой вершине, кроме целевой. Поскольку ни на одной вершине нет двух и более камешков, никакие ходы невозможны, и поэтому нельзя разместить камешек на целевой вершине. Следовательно, число пебблинга должно быть больше, чем n − 1. При наличии n камешков возможны два случая. Если на каждой вершине есть по одному камешку, никакие ходы не требуются. Если какая-либо вершина пуста, то по крайней мере на одной другой вершине должно быть два камешка, и один ход пебблинга позволяет добавить камешек на любую целевую вершину в полном графе.
Граммовая гипотеза
Рональду Грэму приписывают гипотезу о том, что число пебблинга декартова произведения графов не превосходит произведения чисел пебблинга сомножителей в этом произведении. Эта гипотеза получила название гипотезы Грэма о пебблинге. По состоянию на 2019 год она остаётся нерешённой, хотя частные случаи известны.
γ(G) номер пебблинга графика
Крулл и др. ввели понятие покрытия камешками. γ(G), число покрытия графа камешками, — это минимальное количество камешков, необходимое для того, чтобы из любой начальной расстановки камешков, после серии операций перекладывания камешков, граф был покрыт: на каждой вершине находился бы хотя бы один камешек. Результат, известный как теорема о нагромождении, позволяет определить число покрытия камешками для любого графа.
Теорема о сложении
Согласно теореме о наслоении, начальная конфигурация камешков, для которой требуется наибольшее количество ходов для покрытия, возникает, когда все камешки размещены на одной вершине. Исходя из этого наблюдения, определим
для каждой вершины v в G, где d(u, v) обозначает расстояние от u до v. Тогда число пебблинга для покрытия — это наибольшее значение s(v), которое получается.