Мощность графика
В теории графов , разделе математики, k -я степень G к неориентированного графа 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 Δ) , поэтому многие типы разреженных графов, кроме плоских графов, также имеют квадраты, хроматическое число которых пропорционально Δ. .
Хотя хроматическое число квадрата неплоского графа максимальной степени Δ может быть пропорционально Δ 2 в худшем случае он меньше для графов большого обхвата , поскольку ограничен O ( Δ 2 / log Δ) в этом случае. [8]
Определить минимальное количество цветов, необходимых для раскраски квадрата графа, NP-сложно даже в плоском случае. [9]
гамильтоновость
[ редактировать ]Куб любого связного графа обязательно содержит гамильтонов цикл . [10] Это не обязательно тот случай, когда квадрат связного графа является гамильтоновым, и можно NP-полно определить, является ли квадрат гамильтоновым. [11] Тем не менее, по теореме Флейшнера квадрат 2-вершинно-связного графа всегда гамильтонов. [12]
Вычислительная сложность
[ редактировать ]K - я степень графа с n вершинами и m ребрами может быть вычислена за время O ( mn ) , выполняя поиск в ширину, начиная с каждой вершины, чтобы определить расстояния до всех остальных вершин, или немного быстрее, используя более сложные алгоритмы. [13] Альтернативно, если A — матрица смежности графа, модифицированная так, чтобы на его главной диагонали были ненулевые элементы, то ненулевые элементы A к дать матрицу смежности k- й степени графа, [14] откуда следует, что построение k- й степени может быть выполнено за время, находящееся в пределах логарифмического коэффициента времени умножения матриц .
k - ые степени деревьев можно распознать за время, линейное по размеру входного графа. [15]
Учитывая граф, решение о том, является ли он квадратом другого графа, является NP-полным . [16] Более того, NP-полно определить, является ли граф k- й степенью другого графа для заданного числа k ≥ 2 или является ли он k -й степенью двудольного графа для k > 2 . [17]
Индуцированные подграфы
[ редактировать ]
Полуквадрат это G двудольного графа — подграф G 2 индуцированное одной стороной биразделения G . Графы карт — это полуквадраты плоских графов , [18] а графы половинных кубов — это полуквадраты графов гиперкубов . [19]
Степени листьев — это подграфы степеней деревьев, вызванные листьями дерева. Степень k -листа — это степень листа, показатель которой равен k . [20]
Ссылки
[ редактировать ]- ^ Бонди, Адриан; Мурти, USR (2008), Теория графов , Тексты для выпускников по математике, том. 244, Спрингер, с. 82, ISBN 9781846289699 .
- ^ Вайсштейн, Эрик В. , «Сила графа» , MathWorld
- ^ Тодинка, Иоан (2003), «Степень раскраски графов ограниченной ширины клики», Теоретико-графовые концепции в информатике , Конспекты лекций по вычислительной технике. наук, том. 2880, Springer, Berlin, стр. 370–382, номер документа : 10.1007/978-3-540-39890-5_32 , MR 2080095 .
- ^ Jump up to: Перейти обратно: а б Агнарссон, Гейр; Халлдорссон, Магнус М. (2000), «Степень раскраски плоских графов», Труды одиннадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '00) , Сан-Франциско, Калифорния, США, стр. 654–662.
{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) . - ^ Форман, М.; Хагеруп, Т.; Хараламбидес Дж.; Кауфманн, М.; Лейтон, Форт-Стрит ; Симвонис, А.; Вельцль, Э .; Воегингер, Г. (1993), «Рисование графиков на плоскости с высоким разрешением», SIAM Journal on Computing , 22 (5): 1035–1052, doi : 10.1137/0222063 , MR 1237161 .
- ^ Крамер, Флорика; Крамер, Хорст (2008), «Обзор дистанционной раскраски графов», Discrete Mathematics , 308 (2–3): 422–426, doi : 10.1016/j.disc.2006.11.059 , MR 2378044 .
- ^ Моллой, Майкл; Салаватипур, Мохаммад Р. (2005), «Оценка хроматического числа квадрата плоского графа», Журнал комбинаторной теории , серия B, 94 (2): 189–213, doi : 10.1016/j.jctb. 2004.12.005 , ХДЛ : 1807/9473 , МР 2145512 .
- ^ Алон, Нога ; Мохар, Боян (2002), «Хроматическое число степеней графа», Combinatorics, Probability and Computing , 11 (1): 1–10, doi : 10.1017/S0963548301004965 , MR 1888178 , S2CID 2706926 .
- ^ Агнарссон и Халлдорссон (2000) перечисляют публикации, доказывающие NP-твердость для общих графов Маккормика (1983) и Лина и Скиены (1995), а также для плоских графов Раманатана и Ллойда (1992, 1993).
- ^ Бонди и Мерти (2008) , с. 105.
- ^ Underground, Полли (1978), «О графиках с квадратами Гамильтона», Discrete Mathematics , 21 (3): 323, doi : 10.1016/0012-365X(78)90164-4 , MR 0522906 .
- ^ Дистель, Рейнхард (2012), «10. Гамильтоновы циклы», Теория графов (PDF) (исправленное 4-е электронное изд.) .
- ^ Чан, Тимоти М. (2012), «Всепарные кратчайшие пути для невзвешенных неориентированных графов в время", Транзакции ACM по алгоритмам , 8 (4): A34:1–A34:17, doi : 10.1145/2344422.2344424 , MR 2981912 , S2CID 1212001
- ^ Хаммак, Ричард; Имрих, Вильфрид; Клавжар, Санди (2011), Справочник по графам продуктов , дискретной математике и ее приложениям (2-е изд.), CRC Press, стр. 94, ISBN 9781439813058 .
- ^ Чанг, Мау-Шанг; Ко, Минг-Тат; Лу, Сюэ-И (2015), «Алгоритмы линейного времени для решения проблем с корнями деревьев», Algorithmica , 71 (2): 471–495, doi : 10.1007/s00453-013-9815-y , S2CID 253971732 .
- ^ Мотвани, Р.; Судан, М. (1994), «Вычислить корни графов сложно», Discrete Applied Mathematics , 54 : 81–88, doi : 10.1016/0166-218x(94)00023-9 .
- ^ Ле, Ван Банг; Нгуен, Нгок Туй (2010), «Результаты твердости и эффективные алгоритмы для определения степеней графа», Теоретико-графовые концепции в информатике: 35-й международный семинар, WG 2009, Монпелье, Франция, 24–26 июня 2009 г., Пересмотренные статьи , конспекты лекций в области компьютерных наук, вып. 5911, Берлин: Springer, стр. 238–249, doi : 10.1007/978-3-642-11409-0_21 , ISBN. 978-3-642-11408-3 , МР 2587715 .
- ^ Чен, Чжи-Чжун; Гриньи, Микеланджело; Пападимитриу, Христос Х. (2002), «Карта графиков», Журнал ACM , 49 (2): 127–138, arXiv : cs/9910013 , doi : 10.1145/506147.506148 , MR 2147819 , S2CID 2657838 .
- ^ Шпекторов С.В. (1993), «О масштабных вложениях графов в гиперкубы», Европейский журнал комбинаторики , 14 (2): 117–130, doi : 10.1006/eujc.1993.1016 , MR 1206617 .
- ^ Нисимура, Н.; Рагде, П.; Тиликос, Д.М. (2002), «О степенях графа для деревьев с помеченными листьями», Журнал алгоритмов , 42 : 69–108, doi : 10.1006/jagm.2001.1195 .
