Jump to content

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

(Перенаправлено из Power of Graph )
Квадрат графа

В теории графов , разделе математики, 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, / 2 + 1) , причем известно, что хроматическое число не более / 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]

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

[ редактировать ]
K 4 как полуквадрат кубического графа

Полуквадрат это G двудольного графа подграф G 2 индуцированное одной стороной биразделения 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. ^ Jump up to: а б Агнарссон, Гейр; Халлдорссон, Магнус М. (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
  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, 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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 6343602755b85a3a1bbc9e9968d131b3__1721278080
URL1:https://arc.ask3.ru/arc/aa/63/b3/6343602755b85a3a1bbc9e9968d131b3.html
Заголовок, (Title) документа по адресу, URL1:
Graph power - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)