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

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

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

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

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

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

Окраска

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

Оба хроматическое число и вырождение из kя степень планарный граф максимальной степени Δ являются , где оценка вырождения показывает, что a жадная окраска можно использовать алгоритм, чтобы раскрасить график таким количеством цветов.[4] Для частного случая квадрата плоского графа Вегнер в 1977 г. предположил, что хроматическое число квадрата плоского графа не превосходит , и известно, что хроматическое число не превышает .[6][7] В более общем смысле, для любого графа с вырождением d и максимальной степени Δ, вырождение квадрата графа равно О(dΔ), так много типов разреженный граф кроме плоских графов также есть квадраты, хроматическое число которых пропорционально Δ.

Хотя хроматическое число квадрата неплоского графа с максимальной степенью Δ может быть пропорционально Δ2 в худшем случае для графиков с высоким обхват, ограниченная O (∆2/ 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]

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

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

В полуквадрат из двудольный граф грамм является подграфом грамм2 индуцированный одной стороной двудольного грамм. Графики карты полуквадраты планарные графы,[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), «Кратчайшие пути для всех пар для невзвешенных неориентированных графов в время", 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.