Русская Википедия:Степень графа
Степень k (записывается Gk) неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k. Для указания степени графа используется терминология, аналогичная степеням чисел — G2 называется квадратом графа G, G3 называется кубомШаблон:Sfn.
Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф.
Свойства
Если диаметр графа равен d, то его d-ая степень является полным графом[1]. Если семейство графов имеет ограниченную кликовую ширину, то это же верно и для d-х степеней графов семейства для любого фиксированного dШаблон:Sfn.
Раскраска
Раскраску квадрата графа можно использовать для назначения частот участникам беспроволочной сети таким образом, чтобы никакие два участника не мешали бы друг другу и любому другому из общих соседейШаблон:Sfn, а также для поиска графического представления графов с большим угловым разрешениемШаблон:Sfn.
Как хроматическое число, так и вырожденность k-ой степени планарного графа с максимальной степенью вершины Δ равны <math>O(\Delta^{\lfloor k/2\rfloor})</math>, где граница вырождения показывает, что можно использовать алгоритм жадной раскраски для раскраски графа таким числом цветовШаблон:Sfn. Для случая квадрата планарного графа Вегнер в 1977 году высказал гипотезу, что хроматическое число такого графа не превышает <math>\max\left(d+5, \frac{3d}{2}+1\right)</math>, и на текущий момент известно, что хроматическое число не превышает <math>\frac{5d}{3}+O(1)</math>Шаблон:SfnШаблон:Sfn. Более обще, для любого графа с вырождением d и максимальной степенью Δ вырождение квадрата графа равно O(dΔ), так что многие виды разреженных графов, отличные от планарных графов, также имеют пропорциональное Δ хроматическое число квадрата.
Хотя хроматическое число квадрата непланарного графа с максимальной степенью Δ может быть в худшем случае пропорционально Δ2, оно меньше для графов с большим обхватом и для этого случая ограничено числом O(Δ2/log Δ)Шаблон:Sfn.
Задача определения минимального числа цветов для раскраски квадратного графа NP-трудна даже для планарного случая[2]
Гамильтоновость
Куб любого связного графа обязательно содержит гамильтонов циклШаблон:Sfn. Квадрат связного графа не обязательно будет содержать гамильтонов цикл и задача определения, что такой цикл содержится в квадрате, NP-полнаШаблон:Sfn. Тем не менее, согласно теореме Фляйшнера, квадрат вершинно 2-связного графа всегда гамильтоновШаблон:Sfn.
Вычислительная сложность
Степень k графа с n вершинами и m рёбрами можно получить за время O(mn) путём применения поиска в ширину, который осуществляется для каждой вершины графа с целью нахождения расстояний до всех других вершин. Альтернативно, если A — матрица смежности графа, модифицированная таким образом, что на главной диагонали не стоят нулевые элементы, то ненулевые элементы матрицы Ak дают матрицу смежности k-ой степени графаШаблон:Sfn, откуда следует, что построение k-ой степени графа может быть осуществлено за время, равное, с точностью до логарифмического множителя, времени умножения матриц.
Если граф задан, определение, не является ли он квадратом другого графа, является NP-полной задачейШаблон:Sfn. Более того, NP-полной задачей является определение, является ли граф k-ой степенью другого графа для любого заданного числа k ≥ 2, а также является ли он k-ой степенью двудольнго графа для k > 2Шаблон:Sfn.
Порождённые подграфы
Шаблон:Не переведено 5 двудольного графа Шаблон:Mvar — это подграф графа Шаблон:Math, порождённый одной долей графа Шаблон:Mvar. Шаблон:Не переведено 5 — это полуквадраты планарных графовШаблон:Sfn , Шаблон:Не переведено 5 — это полуквадраты графов гиперкубовШаблон:Sfn.
Шаблон:Не переведено 5 — это подграфы степеней деревьев, порождённые листьями деревьевШаблон:Sfn.
Примечания
Литература
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- ↑ Шаблон:Mathworld
- ↑ Агнаррссон и Халлдорссон Шаблон:Harv перечислили в своей статье публикации доказательства NP-трудности для случая общих графов, (статьи Маккормика (McCormick, 1983) и статьи Лина и Скиена (Lin, Skiena, 1995)), и для планарных графов (статьи Раманатхана и Ллойда (Ramanathan, Lloyd, 1992-1993)).
