Оглавление [Скрыть]
Крошение графика
-
Разбиение графа на камешки
- Математическая игра, где на графе с нулем или более камешков в каждой вершине.
- Ход: выбор вершины с двумя камешками, удаление двух и добавление одного к соседней вершине.
-
Число фрагментов графа
- π(G) — наименьшее натуральное число n, при котором можно достичь целевой вершины с камешками.
- Пример: на графе с 2 вершинами и 1 ребром π(G) = 2.
-
История и применение
- Игра предложена Лагариасом и Саксом в 1989 году.
- Используется в криптографии для анализа защищенности функций.
-
π(G) для семейств графов
- π(Kn) = n для полного графа с n вершинами.
- π(Pn) = 2n-1 для графа путей с n вершинами.
- π(Wn) = n для колесного графа с n вершинами.
-
Гипотеза Грэхема
- Число фрагментов декартова произведения графов равно произведению чисел фрагментов множителей.
- Гипотеза остается нераскрытой, известны особые случаи.
-
γ(G) — число фрагментов покрытия графа
- Минимальное количество камешков для покрытия графа G.
- Теорема о стекировании позволяет найти γ(G) для любого графа.
-
γ(G) для семейств графов
- γ(Kn) = 2n-1 для полного графа с n вершинами.
- γ(Pn) = 2n-1 для графа путей с n вершинами.
- γ(Wn) = 4n-9 для колесного графа с n вершинами.