Loading AI tools
Из Википедии, свободной энциклопедии
Степень k (записывается Gk) неориентированного графа G — это другой граф, имеющий тот же самый набор вершин, и две вершины этого графа смежны, если расстояние между этими вершинами в исходном графе G не превышает k. Для указания степени графа используется терминология, аналогичная степеням чисел — G2 называется квадратом графа G, G3 называется кубом[1].
Степень графа не следует путать с умножением графа на себя, который (в отличие от степени графа), в общем случае, имеет много больше вершин, чем исходный граф.
Если диаметр графа равен d, то его d-ая степень является полным графом[2]. Если семейство графов имеет ограниченную кликовую ширину, то это же верно и для d-х степеней графов семейства для любого фиксированного d[3].
Раскраску квадрата графа можно использовать для назначения частот участникам беспроволочной сети таким образом, чтобы никакие два участника не мешали бы друг другу и любому другому из общих соседей[4], а также для поиска графического представления графов с большим угловым разрешением[5].
Как хроматическое число, так и вырожденность k-ой степени планарного графа с максимальной степенью вершины Δ равны , где граница вырождения показывает, что можно использовать алгоритм жадной раскраски для раскраски графа таким числом цветов[4]. Для случая квадрата планарного графа Вегнер в 1977 году высказал гипотезу, что хроматическое число такого графа не превышает , и на текущий момент известно, что хроматическое число не превышает [6][7]. Более обще, для любого графа с вырождением d и максимальной степенью Δ вырождение квадрата графа равно O(dΔ), так что многие виды разреженных графов, отличные от планарных графов, также имеют пропорциональное Δ хроматическое число квадрата.
Хотя хроматическое число квадрата непланарного графа с максимальной степенью Δ может быть в худшем случае пропорционально Δ2, оно меньше для графов с большим обхватом и для этого случая ограничено числом O(Δ2/log Δ)[8].
Задача определения минимального числа цветов для раскраски квадратного графа NP-трудна даже для планарного случая[9]
Куб любого связного графа обязательно содержит гамильтонов цикл[10]. Квадрат связного графа не обязательно будет содержать гамильтонов цикл и задача определения, что такой цикл содержится в квадрате, NP-полна[11]. Тем не менее, согласно теореме Фляйшнера, квадрат вершинно 2-связного графа всегда гамильтонов[12].
Степень k графа с n вершинами и m рёбрами можно получить за время O(mn) путём применения поиска в ширину, который осуществляется для каждой вершины графа с целью нахождения расстояний до всех других вершин. Альтернативно, если A — матрица смежности графа, модифицированная таким образом, что на главной диагонали не стоят нулевые элементы, то ненулевые элементы матрицы Ak дают матрицу смежности k-ой степени графа[13], откуда следует, что построение k-ой степени графа может быть осуществлено за время, равное, с точностью до логарифмического множителя, времени умножения матриц.
Если граф задан, определение, не является ли он квадратом другого графа, является NP-полной задачей[14]. Более того, NP-полной задачей является определение, является ли граф k-ой степенью другого графа для любого заданного числа k ≥ 2, а также является ли он k-ой степенью двудольнго графа для k > 2[15].
Полуквадрат[англ.] двудольного графа G — это подграф графа G2, порождённый одной долей графа G. Графы карт[англ.] — это полуквадраты планарных графов[16] , уполовиненные графы кубов[англ.] — это полуквадраты графов гиперкубов[17].
Степени листьев[англ.] — это подграфы степеней деревьев, порождённые листьями деревьев[18].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
