В теории графов , разделе математики, k -я степень Gk неориентированного графа G — это другой граф, который имеет тот же набор вершин , но в котором две вершины являются смежными, когда их расстояние в G не превышает k . Для обозначения степеней графов используется терминология, аналогичная терминологии возведения чисел в степень: G 2 называется квадратом G , G 3 называется кубом G и т . д . [ 1 ]
Степени графа следует отличать от произведений графа на самого себя, которые (в отличие от степеней) обычно имеют гораздо больше вершин, чем исходный граф.
Если граф имеет диаметр d , то его d -я степень является полным графом . [2] Если семейство графов имеет ограниченную ширину клика , то то же самое имеет и его d -я степень для любого фиксированного d . [3]
Раскраска графа на квадрате графа может быть использована для присвоения частот участникам сетей беспроводной связи так, чтобы два участника не мешали друг другу ни у одного из их общих соседей [4] , а также для поиска рисунков графов с высоким угловым разрешением . [5]
И хроматическое число , и вырождение k - й степени планарного графа максимальной степени Δ равны O (Δ ⌊ k /2⌋ ) , где граница вырождения показывает, что для раскраски графа можно использовать жадный алгоритм раскраски с этим много цветов. [4] Для частного случая квадрата плоского графа в 1977 году Вегнер предположил, что хроматическое число квадрата плоского графа не превосходит max(Δ + 5,3Δ/2+ 1) , причем известно, что хроматическое число не более5Δ/3+ О (1) . [6] [7] В более общем смысле, для любого графа с вырождением d и максимальной степенью Δ вырождение квадрата графа равно O ( d Δ) , поэтому многие типы разреженных графов , кроме плоских графов, также имеют квадраты, у которых хроматическое число пропорционально Δ .
Хотя хроматическое число квадрата неплоского графа с максимальной степенью Δ может быть пропорционально Δ 2 в худшем случае, оно меньше для графов большого обхвата и в этом случае ограничено величиной O (Δ 2 / log Δ) . [8]
Определить минимальное количество цветов, необходимых для раскраски квадрата графа, NP-сложно даже в плоском случае. [9]
Куб любого связного графа обязательно содержит гамильтонов цикл . [10] Это не обязательно тот случай, когда квадрат связного графа является гамильтоновым, и NP-полно определить, является ли квадрат гамильтоновым. [11] Тем не менее, по теореме Фляйшнера , квадрат 2-вершинно-связного графа всегда гамильтонов. [12]
K - я степень графа с n вершинами и m ребрами может быть вычислена за время O ( mn ) , выполняя поиск в ширину , начиная с каждой вершины, чтобы определить расстояния до всех остальных вершин, или немного быстрее, используя более сложные алгоритмы. [13] Альтернативно, если A — матрица смежности графа, модифицированная так, чтобы на его главной диагонали были ненулевые элементы, то ненулевые элементы Ak дают матрицу смежности k -й степени графа, [14] из которой отсюда следует, что построение k -й степени может быть выполнено за время, находящееся в пределах логарифмического коэффициента времени умножения матриц .
k - ые степени деревьев можно распознать за время, линейное по размеру входного графа.[15]
Учитывая граф, решение о том, является ли он квадратом другого графа, является NP-полным .[16] Более того, NP-полно определить, является ли граф k- й степенью другого графа для данного числа k ≥ 2 или является ли он k -й степенью двудольного графа для k > 2 . [17]
Полуквадрат двудольного графа G — это подграф графа G2 , индуцированный одной стороной двудольного графа G. Графы карт — это полуквадраты плоских графов , [18] , а графы половинных кубов — это полуквадраты графов гиперкубов . [19]
Степени листьев — это подграфы степеней деревьев, вызванные листьями дерева. Степень k -листа — это степень листа, показатель которой равен k . [20]
{{citation}}
: CS1 maint: отсутствует местоположение издателя ( ссылка ).