Вырожденность (теория графов)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
2-Вырожденный граф — каждая вершина имеет не более двух соседей слева, так что самая правая вершина любого подграфа имеет степень два и менее. Его 2-ядро, подграф, остающийся после удаления вершин со степенью, меньшей двух, выделено цветом.

k-Вырожденный граф — это неориентированный граф, в котором каждый подграф имеет вершины со степенью, не превосходящей k. Вырожденность графа — это наименьшее значение k, для которого граф является k-вырожденным. Вырожденность графа отражает, насколько граф разрежен и (с точностью до постоянного множителя) отражает другие меры разреженности, такие как древесность графа.

Вырожденность известна также под именем k-ядерное число[1][2][3], ширина[4] и зацепление[5], и, по существу, это то же самое, что и число раскраски[6] или число Секереша — Вилфа. k-Вырожденные графы называются также k-индуктивными графами[7]. Вырожденность графа может быть вычислена за линейное время с помощью алгоритма, который последовательно удаляет вершины с минимальной степенью[8]. Компонента связности, оставшаяся после удаления всех вершин со степенью , меньшей k, называется k-ядром графа, и вырожденность графа равна наибольшему значению k, для которого существует k-ядро.

Примеры[править | править код]

Любой лес либо имеет изолированную вершину (без смежных рёбер), либо листовую вершину (инцидентную в точности одному ребру), так что леса и деревья являются 1-вырожденными графами.

Любой конечный планарный граф имеет вершину степени пять или менее, так что любой планарный граф является 5-вырожденным и вырожденность любого планарного графа не превосходит пяти. Подобно этому, вырожденность любого внешнепланарного графа не превосходит двух[9], а вырожденность графов Аполлония равна трём.

Модель Барабаши — Альберт генерации случайных безмасштабных сетей[10] имеет в качестве параметра число m, такое, что каждая вершина, добавленная к графу, связана рёбрами с m добавленных ранее вершин. Отсюда следует, что любой подграф сети, полученный таким способом, имеет степень вершин, не меньшую m (это степень последней вершины, добавленной в граф), так что сети Барабаши — Альберт автоматически m-вырожденные.

Любой k-регулярный граф имеет вырожденность в точности k. Более строго, вырожденность графа равна наибольшей степени вершины тогда и только тогда, когда по меньшей мере одна из компонент связности графа является регулярной и имеет степень самого графа. Для всех остальных графов вырожденность строго меньше наибольшей степени вершин графа[11]

Определения[править | править код]

Число раскрашивания графа G ввели Эрдёш и Хайнал[6] как наибольшее κ, для которого существует упорядочение вершин графа G, при котором каждая вершина имеет меньше κ соседей, предшествующих вершине в порядке. Следует отличать это число от хроматического числа графа G, минимального числа цветов, необходимых для раскраски вершин, при которой никакие две смежные вершины не выкрашены в одинаковый цвет. Упорядочение, определяющее число раскрашивания, даёт порядок раскрашивания вершин графа G в число цветов, равное числу раскрашивания, но, в общем случае, хроматическое число может быть меньше этого числа.

Вырожденность графа G Лик и Уайт[9] определили как наименьшее число k, для которого любой порождённый подграф графа G содержит вершину с k и менее соседями. Определение не изменится, если вместо порождённых подграфов брать произвольные подграфы, поскольку непорождённый подграф может иметь степени вершин, не превосходящие степеней вершин порождённого с тем же набором вершин подграфа.

Два понятия, число раскрашивания и вырожденность, эквивалентны — в любом конечном графе вырожденность на единицу меньше числа раскрашивания[12][13]. Если граф имеет упорядочение с числом раскрашивания κ, то в каждом подграфе H вершина, принадлежащая H и являющаяся последней в упорядочении, имеет не более κ − 1 соседей в H. В другом направлении, если G равно k-вырожденности, то упорядочение с числом раскрашивания k + 1 можно получить путём последовательного нахождения вершины v с максимум k соседями, удаления вершины v из графа, упорядочения оставшихся вершин и добавления вершины v в конец порядка.

Третье эквивалентное определение k-вырожденности графа G (или что число раскрашивания не превосходит k + 1) — граф k-вырожден тогда и только тогда, когда рёбра графа G могут быть ориентированы с образованием направленного ациклического графа с полустепенью исхода, не превосходящей k[14]. Такая ориентация может быть получена путём ориентации каждого ребра в сторону более ранней из двух вершин ребра согласно упорядочению. В другом направлении, если задана ориентация с полуисходом выхода k, упорядочение с числом раскрашивания k + 1 может быть получено как топлогическое упорядочение ориентированного ациклического графа.

k-Ядра[править | править код]

k-Ядро графа G — это максимальный связный подграф графа G, в котором все вершины имеют степень по меньшей мере k. Эквивалентно, это одна из связных компонент подграфа G, образованного последовательным удалением всех вершин со степенью, меньшей k. Если существует непустое k-ядро, ясно, что G имеет вырожденность, не меньшую k, а вырожденность графа G — это наибольшее число k, для которого G имеет k-ядро.

Вершина имеет ядерность , если вершина принадлежит -ядру, но не принадлежит - ядру.

Понятие k-ядра было введено для изучения группировки в социальных сетях[15] и для описания развёртывания случайных графов[16][17][18]. Понятие было также перенесено в биоинформатику[1][2] и визуализацию сетей[19][20].

Алгоритмы[править | править код]

Как описывают Матула и Бек[8], можно найти за линейное время упорядочение вершин в конечном графе G, оптимизирующее число раскрашивания упорядочения, если использовать контейнерную очередь[en] для нахождения и удаления вершин наименьшей степени. Вырожденность тогда — это наибольшая степень любой вершины на момент её удаления.

Более детально, алгоритм работает следующим образом:

  • Создаём выходной список L.
  • Вычисляем число dv для любой вершины v графа G, число соседей вершины v, ещё не находящихся в L. Начально эти числа просто равны степеням вершин.
  • Создаём массив D, в котором D[i] содержит список вершин v, не входящих в список L, для которых dv = i.
  • Присваиваем k значение 0.
  • Повторяем n раз:
    • Просматриваем элементы массива D[0], D[1], ..., пока не найдём i, для которого D[i] не пусто.
    • Присваиваем k максимальное из двух значений (k,i)
    • Выбираем вершину v из D[i]. Добавляем v в начало очереди L и удаляем её из D[i].
    • Для каждой вершины w, соседней v и не находящейся в L, вычитаем единицу из dw и переносим w в элемент массива D, который соответствует новому значению dw.

При завершении алгоритма k содержит вырожденность графа G, а список L содержит вершины в оптимальном порядке для числа раскрашивания. В графе G i-ядра — это подсписки списка L, состоящие из вершин, добавленных в L после того, как k первый раз принимает значение, большее или равное i.

Инициализация переменных L, dv, D и k может быть легко сделана за линейное время. Нахождение очередной удаляемой вершины v и пересчёт элементов D, содержащих соседей вершины v, занимает время, пропорциональное значению dv на этом шаге, но сумма таких значений равна числу рёбер графа, так что общее время линейно.

Связь с другими параметрами графа[править | править код]

Если граф G является ориентированным ацикличным с полустепенью исхода k, то его дуги могут быть разбиты на k лесов путём выбора одного леса для каждой исходящей дуги каждой вершины. Таким образом, древесность графа G не превосходит его вырожденности. В обратном направлении, граф с n вершинами, который можно разбить на k лесов, имеет не более k(n − 1) рёбер, а потому имеет вершины со степенью, не превосходящей 2k− 1. То есть вырожденность вдвое меньше древесности графа. Можно вычислить также за полиномиальное время ориентацию графа, минимизирующую степень полувыхода, не требуя ацикличности графа. Рёбра графа с такой ориентацией можно разбить тем же способом на k псевдолесов. И обратно, любое разбиение рёбер графа на k псевдолесов приводит к ориентации с наибольшей полустепенью исхода k (путём выбора ориентации с полустепенью выхода 1 для каждого псевдолеса), так что наименьшая полустепень исхода такой ориентации является псевдодревесностью, которая, снова, не превосходит вырожденности[14][21][22][23][24]. Толщина также (с точностью до постоянного множителя) пропорциональна древесности, так что то же самое верно и для вырожденности[25].

k-Вырожденный граф имеет хроматическое число, не превосходящее k + 1. Это можно показать простой индукцией по числу вершин в точности как при доказательстве теоремы о шести красках для планарных графов. Поскольку хроматическое число является верхней границей порядка наибольшей клики, этот порядок не превосходит вырожденности плюс единица. При использовании алгоритма жадной раскраски на упорядочение с оптимальным числом раскрашивания, можно раскрасить k-вырожденный граф, используя не более k + 1 цветов[6][26].

Вершинно k-связный граф — это граф, который нельзя разбить на несколько компонент путём удаления менее k вершин, или, эквивалентно, это граф, в котором каждая пара вершин может быть соединена k путями, не имеющими общих вершин. Поскольку в этих путях должны исходить эти две вершины через различные рёбра, вершинно k-связный граф должен иметь вырожденность по меньшей мере k. Понятие, близкое k-ядрам, но основывающееся на связности вершин, изучается в теории социальных сетей под названием структурные связи[en][27].

Если древесная ширина или путевая ширина графа не превосходит k, тогда он является подграфом хордального графа, имеющего совершенный порядок исключения, при котором каждая вершина имеет не более k предшествующих соседей. Таким образом, вырожденность не превосходит древесной ширины и путевой ширины. Однако существуют графы с ограниченной вырожденностью и неограниченной древесной шириной, как, например, решётки[28].

Гипотеза Эрдёша — Бура касается связи вырожденности графа G и числа Рамсея графа G, наибольшего n, для которого любая двухцветная раскраска рёбер полного графа с n вершинами должна содержать монохромную копию графа G. Конкретно, гипотеза утверждает, что для любого фиксированного значения k число Рамсея k-вырожденных графов растёт линейно от числа вершин графов[29]. Гипотезу доказал Ли[30].

Бесконечные графы[править | править код]

Хотя понятия вырожденности и числа раскрашивания часто подразумевают контекст конечных графов, начальной целью Эрдёша и Хайнала[6] была теория бесконечных графов. Для бесконечного графа G можно определить число раскрашивания аналогично определению для конечных графов как наименьшее кардинальное число α, для которого существует упорядочение вершин графа G, являющееся вполне упорядоченным, в котором каждая вершина имеет менее α соседей среди предыдущих вершин в упорядочении. Неравенство между числом раскрашивания и хроматическим числом имеет место и для бесконечного случая. Эрдёш и Хайнал[6] утверждали это, и на время публикации их работы факт был хорошо известен.

Вырождение случайных подмножеств бесконечных решёток изучается в теории с названием инициирующее просачивание[en].

Примечания[править | править код]

  1. 1 2 Altaf-Ul-Amin, Nishikata, Koma, Miyasato и др., 2003.
  2. 1 2 Wuchty, Almaas, 2005.
  3. Bader, Hogue, 2003.
  4. Freuder, 1982.
  5. Kirousis, Thilikos, 1996.
  6. 1 2 3 4 5 Erdős, Hajnal, 1966.
  7. Irani, 1994.
  8. 1 2 Matula, Beck, 1983.
  9. 1 2 Lick, White, 1970.
  10. Barabási, Albert, 1999.
  11. Йенсен и Тофт (Jensen, Toft 2011), p. 78: «Легко видеть, что col(G) = Δ(G) + 1 тогда и только тогда, когда G имеет Δ(G)-регулярную компоненту». В обозначениях Йенсера и Тофта col(G) равно вырождению + 1, а Δ(G) равно максимальной степени вершины.
  12. Matula, 1968.
  13. Lick, White, 1970, с. 1084 Proposition 1.
  14. 1 2 Chrobak, Eppstein, 1991.
  15. Seidman, 1983.
  16. Bollobás, 1984.
  17. Łuczak, 1991.
  18. Dorogovtsev, Goltsev, Mendes, 2006.
  19. Gaertler, Patrignani, 2004.
  20. Alvarez-Hamelin, Dall'Asta, Barrat, Vespignani, 2005.
  21. Gabow, Westermann, 1992.
  22. Venkateswaran, 2004.
  23. Asahiro, Miyano, Ono, Zenmyo, 2006.
  24. Kowalik, 2006.
  25. Dean, Hutchinson, Scheinerman, 1991.
  26. Szekeres, Wilf, 1968.
  27. Moody, White, 2003.
  28. Robertson, Seymour, 1984.
  29. Burr, Erdős, 1975.
  30. Lee, 2017.

Литература[править | править код]