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

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

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

В теории графов ^, разделе математики, 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 Δ) , поэтому многие типы разреженных графов , кроме плоских графов, также имеют квадраты, у которых хроматическое число пропорционально Δ .

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

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

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

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

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

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

1. Бонди, Адриан; Мурти, USR (2008), Теория графов, Тексты для аспирантов по математике, том. 244, Спрингер, с. 82, ISBN 9781846289699.
2. Вайсштейн, Эрик В. , «Сила графика», MathWorld
3. Тодинка, Иоан (2003), «Степень раскраски графов ограниченной ширины клики», Теоретико-графовые концепции в информатике , Конспекты лекций по вычислениям. наук., вып. 2880, Springer, Berlin, стр. 370–382, номер документа : 10.1007/978-3-540-39890-5_32, MR  2080095..
4. Агнарссон, Гейр; Халлдорссон, Магнус М. (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), «Обзор дистанционной раскраски графов», Discrete Mathematics , 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, ЛДЛ : 1807/9473 , МР  2145512.
8. Алон, Нога ; Мохар, Боян (2002), «Хроматическое число степеней графа», Combinatorics, Probability and Computing , 11 (1): 1–10, doi : 10.1017/S0963548301004965, MR  1888178, S2CID  2706926.
9. Агнарссон и Халлдорссон (2000) перечисляют публикации, доказывающие NP-твердость для общих графов Маккормика (1983) и Лина и Скиены (1995), а также для плоских графов Раманатана и Ллойда (1992, 1993).
10. Бонди и Мерти (2008), с. 105.
11. Underground, Полли (1978), «О графиках с квадратами Гамильтона», Discrete Mathematics , 21 (3): 323, doi : 10.1016/0012-365X(78)90164-4 , MR  0522906.
12. Дистель, Рейнхард (2012), «10. Гамильтоновы циклы», Теория графов (PDF) (исправленное 4-е электронное изд.).
13. Чан, Тимоти М. (2012), «Кратчайшие пути для всех пар для невзвешенных неориентированных графов во времени», Транзакции ACM в алгоритмах , 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), «Вычислить корни графов сложно», Discrete Applied Mathematics , 54 : 81–88, doi : 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 , doi : 10.1145/506147.506148, MR  2147819, S2CID  2657838.
19. Шпекторов, С.В. (1993), «О масштабных вложениях графов в гиперкубы», Европейский журнал комбинаторики , 14 (2): 117–130, doi : 10.1006/eujc.1993.1016 , MR  1206617.
20. Нисимура, Н.; Рагде, П.; Тиликос, Д. М. (2002), «О степенях графа для деревьев с размеченными листьями», Журнал алгоритмов , 42 : 69–108, doi : 10.1006/jagm.2001.1195.