Степень графа

Квадрат графа

Степень k (записывается G^k) неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k. Для указания степени графа используется терминология, аналогичная степеням чисел — G² называется квадратом графа G, G³ называется кубом.

Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф.

Свойства

Если диаметр графа равен d, то его d-ая степень является полным графом. Если семейство графов имеет ограниченную кликовую ширину, то это же верно и для d-х степеней графов семейства для любого фиксированного d.

Раскраска

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

Как хроматическое число, так и вырожденность k-ой степени планарного графа с максимальной степенью вершины Δ равны $O(\Delta ^{\lfloor k/2\rfloor })$, где граница вырождения показывает, что можно использовать алгоритм жадной раскраски для раскраски графа таким числом цветов. Для случая квадрата планарного графа Вегнер в 1977 году высказал гипотезу, что хроматическое число такого графа не превышает $\max \left(d+5,{\frac {3d}{2}}+1\right)$, и на текущий момент известно, что хроматическое число не превышает ${\frac {5d}{3}}+O(1)$. Более обще, для любого графа с вырождением d и максимальной степенью Δ вырождение квадрата графа равно O(dΔ), так что многие виды разреженных графов, отличные от планарных графов, также имеют пропорциональное Δ хроматическое число квадрата.

Хотя хроматическое число квадрата непланарного графа с максимальной степенью Δ может быть в худшем случае пропорционально Δ², оно меньше для графов с большим обхватом и для этого случая ограничено числом O(Δ²/log Δ).

Задача определения минимального числа цветов для раскраски квадратного графа NP-трудна даже для планарного случая

Гамильтоновость

Куб любого связного графа обязательно содержит гамильтонов цикл. Квадрат связного графа не обязательно будет содержать гамильтонов цикл и задача определения, что такой цикл содержится в квадрате, NP-полна. Тем не менее, согласно теореме Фляйшнера, квадрат вершинно 2-связного графа всегда гамильтонов.

Вычислительная сложность

Степень k графа с n вершинами и m рёбрами можно получить за время O(mn) путём применения поиска в ширину, который осуществляется для каждой вершины графа с целью нахождения расстояний до всех других вершин. Альтернативно, если A — матрица смежности графа, модифицированная таким образом, что на главной диагонали не стоят нулевые элементы, то ненулевые элементы матрицы A^k дают матрицу смежности k-ой степени графа, откуда следует, что построение k-ой степени графа может быть осуществлено за время, равное, с точностью до логарифмического множителя, времени умножения матриц.

Если граф задан, определение, не является ли он квадратом другого графа, является NP-полной задачей. Более того, NP-полной задачей является определение, является ли граф k-ой степенью другого графа для любого заданного числа k ≥ 2, а также является ли он k-ой степенью двудольнго графа для k > 2.

Порождённые подграфы

K₄ как полуквадрат графа куба

Полуквадрат двудольного графа G — это подграф графа G², порождённый одной долей графа G. Графы карт — это полуквадраты планарных графов , уполовиненные графы кубов — это полуквадраты графов гиперкубов.

Степени листьев — это подграфы степеней деревьев, порождённые листьями деревьев.