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

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

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

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

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

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

Окраска

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

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

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

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

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

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

Вычислительная сложность

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

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

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

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

K₄ как полуквадрат куб граф

В полуквадрат из двудольный граф грамм является подграфом грамм² индуцированный одной стороной двудольного грамм. Графики карты полуквадраты планарные графы,^[18] и вдвое кубические графики полуквадраты графы гиперкуба.^[19]

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

Рекомендации

1. Бонди, Адриан; Мурти, США (2008), Теория графов, Тексты для выпускников по математике, 244, Springer, стр. 82, ISBN  9781846289699.
2. Вайсштейн, Эрик В. «График мощности». MathWorld.
3. Тодинка, Иоан (2003), "Раскрашивающие способности графов ограниченной ширины клики", Теоретико-графические концепции в информатике, Конспект лекций по вычисл. Наук, 2880, Springer, Berlin, стр. 370–382, Дои:10.1007/978-3-540-39890-5_32, МИСТЕР  2080095.
4. Агнарссон, Гейр; Халлдорссон, Магнус М. (2000), "Раскрашивающие способности плоских графов", Материалы одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '00), Сан-Франциско, Калифорния, США, стр. 654–662..
5. Formann, M .; Hagerup, T .; Haralambides, J .; Кауфманн, М .; Лейтон, Ф. Т.; Symvonis, A .; Вельцль, Э.; Вегингер, Г. (1993), «Рисование графиков на плоскости с высоким разрешением», SIAM Журнал по вычислениям, 22 (5): 1035–1052, Дои:10.1137/0222063, МИСТЕР  1237161.
6. Крамер, Флорика; Крамер, Хорст (2008), "Обзор дистанционной раскраски графов", Дискретная математика, 308 (2–3): 422–426, Дои:10.1016 / j.disc.2006.11.059, МИСТЕР  2378044.
7. Моллой, Майкл; Салаватипур, Мохаммад Р. (2005), "Оценка хроматического числа квадрата плоского графа", Журнал комбинаторной теории, Серия B, 94 (2): 189–213, Дои:10.1016 / j.jctb.2004.12.005, HDL:1807/9473, МИСТЕР  2145512.
8. Алон, Нога; Мохар, Боян (2002), «Хроматическое число степеней графа», Комбинаторика, теория вероятностей и вычисления, 11 (1): 1–10, Дои:10.1017 / S0963548301004965, МИСТЕР  1888178.
9. Агнарссон и Халльдорссон (2000) перечислите публикации, доказывающие NP-твердость общих графов Маккормиком (1983) и Лином и Скиеной (1995), а также планарными графами Раманатаном и Ллойдом (1992, 1993).
10. Бонди и Мурти (2008), п. 105.
11. Метро, ​​Полли (1978), «О графах с гамильтоновыми квадратами», Дискретная математика, 21 (3): 323, Дои:10.1016 / 0012-365X (78) 90164-4, МИСТЕР  0522906.
12. Дистель, Рейнхард (2012), «10. Гамильтоновы циклы», Теория графов (PDF) (исправленное 4-е электронное изд.).
13. Чан, Тимоти М. (2012), «Кратчайшие пути для всех пар для невзвешенных неориентированных графов в ${\displaystyle o(mn)}$ время", ACM-транзакции на алгоритмах, 8 (4): A34: 1 – A34: 17, Дои:10.1145/2344422.2344424, МИСТЕР  2981912
14. Хаммак, Ричард; Имрих, Вильфрид; Клавжар, Санди (2011), Справочник графиков продуктов, Дискретная математика и ее приложения (2-е изд.), CRC Press, стр. 94, ISBN  9781439813058.
15. Чанг, Мо-Шан; Ко, Мин-Тат; Лу, Сюэ-И (2015), "Алгоритмы линейного времени для задач корня дерева", Алгоритмика, 71 (2): 471–495, Дои:10.1007 / s00453-013-9815-y.
16. Motwani, R .; Судан, М. (1994), "Вычислить корни графов сложно", Дискретная прикладная математика, 54: 81–88, Дои:10.1016 / 0166-218x (94) 00023-9.
17. Ле, Ван Банг; Нгуен, Нгок Туй (2010), "Результаты твердости и эффективные алгоритмы для степеней графа", Теоретико-графические концепции в компьютерных науках: 35-й международный семинар, WG 2009, Монпелье, Франция, 24-26 июня 2009 г., исправленные статьи, Конспект лекций по информатике, 5911, Берлин: Springer, стр. 238–249, Дои: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, Дои:10.1145/506147.506148, МИСТЕР  2147819.
19. Шпекторов, С. В. (1993), "О масштабных вложениях графов в гиперкубы", Европейский журнал комбинаторики, 14 (2): 117–130, Дои:10.1006 / eujc.1993.1016, МИСТЕР  1206617.
20. Nishimura, N .; Ragde, P .; Тиликос, Д. (2002), "О степенях графа для деревьев с листами", Журнал алгоритмов, 42: 69–108, Дои:10.1006 / jagm.2001.1195.