Мощность графика

Операция графа: соединение всех пар узлов на расстоянии ≤ k

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

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

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

Характеристики

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

Раскрашивание

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

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

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

Определение минимального количества цветов, необходимых для раскраски квадрата графа, является NP-трудной задачей даже в плоском случае. ^[9]

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

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

Сложность вычислений

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

Степень деревьев k может быть распознана за время, линейно зависящее от размера входного графа. ^[15]

Для данного графа решение вопроса, является ли он квадратом другого графа, является NP-полной задачей . ^[16] Более того, NP-полной задачей является определение того, является ли граф k -й степенью другого графа, для заданного числа k ≥ 2 , или является ли он k- й степенью двудольного графа , для k > 2. [ ^17]

Индуцированные подграфы

K ₄ как половина квадрата кубического графа

Половина квадрата двудольного графа G является подграфом G ^{2 ,} индуцированным одной стороной двудольного графа G. Графы карт являются полуквадратами планарных графов , ^[18] а графы половинных кубов являются полуквадратами графов гиперкубов . ^[19]

Степени листьев — это подграфы степеней деревьев, индуцированные листьями дерева. Степени листьев k — это степени листьев, показатель степени которых равен k . ^[20]

Ссылки

1. Бонди, Адриан; Мурти, USR (2008), Теория графов, Graduate Texts in Mathematics, т. 244, Springer, стр. 82, ISBN 9781846289699.
2. Вайсштейн, Эрик В. , «Сила графа», MathWorld
3. Todinca, Ioan (2003), "Coloring powers of graphs of bounded clique-width", Графовые теоретические концепции в информатике , Lecture Notes in Comput. Sci., т. 2880, Springer, Берлин, стр. 370–382, doi :10.1007/978-3-540-39890-5_32, MR  2080095.
4. Agnarsson, Geir; Halldórsson, Magnús M. (2000), «Раскрашивающие способности планарных графов», Труды одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '00) , Сан-Франциско, Калифорния, США, стр. 654–662{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ).
5. Форман, М.; Хагеруп, Т.; Хараламбидес, Дж.; Кауфман, М.; Лейтон, Ф. Т .; Симвонис, А.; Вельцль, Э .; Воегингер, Г. (1993), «Рисование графиков на плоскости с высоким разрешением», SIAM Journal on Computing , 22 (5): 1035–1052, doi :10.1137/0222063, MR  1237161.
6. Крамер, Флорика; Крамер, Хорст (2008), «Обзор дистанционной раскраски графов», Дискретная математика , 308 (2–3): 422–426, doi : 10.1016/j.disc.2006.11.059 , MR  2378044.
7. Моллой, Майкл; Салаватипур, Мохаммад Р. (2005), «Граница хроматического числа квадрата планарного графа», Журнал комбинаторной теории , Серия B, 94 (2): 189–213, doi : 10.1016/j.jctb.2004.12.005, hdl : 1807/9473 , MR  2145512.
8. Алон, Нога ; Мохар, Боян (2002), «Хроматическое число степеней графа», Комбинаторика, вероятность и вычисления , 11 (1): 1–10, doi :10.1017/S0963548301004965, MR  1888178, S2CID  2706926.
9. Агнарссон и Халлдорссон (2000) перечисляют публикации, доказывающие NP-трудность для общих графов Маккормика (1983) и Лина и Скиены (1995), а также для планарных графов Раманатана и Ллойда (1992, 1993).
10. Бонди и Мурти (2008), стр. 105.
11. Underground, Polly (1978), «О графах с гамильтоновыми квадратами», Discrete Mathematics , 21 (3): 323, doi : 10.1016/0012-365X(78)90164-4 , MR  0522906.
12. Дистель, Рейнхард (2012), "10. Гамильтоновы циклы", Теория графов (PDF) (исправленное 4-е электронное издание).
13. Чан, Тимоти М. (2012), «Кратчайшие пути для всех пар невзвешенных неориентированных графов во времени», ACM Transactions on Algorithms , 8 (4): A34:1–A34:17, doi :10.1145/2344422.2344424, MR  2981912, S2CID  1212001 ${\displaystyle o(mn)}$
14. Хаммак, Ричард; Имрих, Вильфрид; Клавжар, Санди (2011), Справочник по графам произведений, Дискретная математика и ее приложения (2-е изд.), CRC Press, стр. 94, ISBN 9781439813058.
15. Чанг, Мо-Шан; Ко, Мин-Тат; Лу, Сюэ-И (2015), «Линейные алгоритмы для задач с корнями деревьев», Algorithmica , 71 (2): 471–495, doi :10.1007/s00453-013-9815-y, S2CID  253971732.
16. Мотвани, Р.; Судан, М. (1994), «Вычисление корней графов — сложная задача», Дискретная прикладная математика , 54 : 81–88, doi : 10.1016/0166-218x(94)00023-9.
17. Le, Van Bang; Nguyen, Ngoc Tuy (2010), "Результаты по твердости и эффективные алгоритмы для степеней графов", Graph-Theoretic Concepts in Computer Science: 35th International Workshop, WG 2009, Монпелье, Франция, 24-26 июня 2009 г., Revised Papers , Lecture Notes in Computer Science, т. 5911, Берлин: Springer, стр. 238–249, doi :10.1007/978-3-642-11409-0_21, ISBN 978-3-642-11408-3, г-н  2587715.
18. Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Карты графиков», Журнал ACM , 49 (2): 127–138, arXiv : cs/9910013 , doi : 10.1145/506147.506148, MR  2147819, S2CID  2657838.
19. Шпекторов, С.В. (1993), «О масштабных вложениях графов в гиперкубы», European Journal of Combinatorics , 14 (2): 117–130, doi : 10.1006/eujc.1993.1016 , MR  1206617.
20. Нишимура, Н.; Рагде, П.; Тиликос, Д.М. (2002), «О степенях графов для деревьев с метками листьев», Журнал алгоритмов , 42 : 69–108, doi :10.1006/jagm.2001.1195.