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

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

Свойства

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

Раскраска

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

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

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

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

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

Примечания

Литература