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

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

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

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

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

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

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

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

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

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

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

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

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