stringtranslate.com

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

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

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

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

Примеры

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

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

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

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

Определения и эквивалентности

Число окраски графа G было определено Эрдёшем и Хайналом (1966) как наименьшее κ, для которого существует упорядочение вершин графа G , в котором каждая вершина имеет менее κ соседей, которые находятся раньше в упорядочении. Его следует отличать от хроматического числа графа G , минимального числа цветов, необходимых для окраски вершин так, чтобы никакие две смежные вершины не имели одинаковый цвет; порядок, который определяет число окраски, обеспечивает порядок окраски вершин графа G с числом окраски, но в общем случае хроматическое число может быть меньше.

Вырожденность графа G была определена Ликом и Уайтом (1970) как наименьшее k , такое, что каждый индуцированный подграф G содержит вершину с k или меньшим количеством соседей. Определение было бы тем же самым, если бы вместо индуцированных подграфов допускались произвольные подграфы, поскольку неиндуцированный подграф может иметь только степени вершин, которые меньше или равны степеням вершин в подграфе , индуцированном тем же набором вершин.

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

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

к-Ядра

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

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

Концепция k -ядра была введена для изучения кластерной структуры социальных сетей [12] и описания эволюции случайных графов . [13] Она также применялась в биоинформатике , [14] визуализации сетей , [15] и устойчивости сетей в экологии . [16] Обзор темы, охватывающий основные концепции, важные алгоритмические методы, а также некоторые области применения, можно найти в Malliaros et al. (2019).

Перколяция Bootstrap — это случайный процесс, изучаемый как эпидемическая модель [17] и как модель отказоустойчивости для распределенных вычислений . [18] Он состоит из выбора случайного подмножества активных ячеек из решетки или другого пространства, а затем рассмотрения k -ядра индуцированного подграфа этого подмножества. [19]

Алгоритмы

Матула и Бек (1983) описывают алгоритм для вывода порядка вырожденности графа с множеством вершин V и множеством ребер E во времени и словах пространства, сохраняя вершины в очереди с индексацией по степени и многократно удаляя вершину с наименьшей степенью. Вырожденность k задается наивысшей степенью любой вершины во время ее удаления.

Более подробно алгоритм выглядит следующим образом:

В конце алгоритма любая вершина будет иметь не более k ребер к вершинам . Ядра графа G — это подграфы , которые индуцируются вершинами , где i — первая вершина со степенью на момент ее добавления к L .

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

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

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

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

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

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

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

Бесконечные графики

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

Вырождение случайных подмножеств бесконечных решеток изучалось под названием бутстраповской перколяции .

Смотрите также

Примечания

  1. ^ Бадер и Хог (2003).
  2. ^ Фрейдер (1982).
  3. ^ Кирусис и Тиликос (1996).
  4. ^ Эрдёш и Хайнал (1966).
  5. ^ Ирани (1994).
  6. ^ Матула и Бек (1983).
  7. ↑ Лик и Уайт (1970).
  8. ^ Барабаши и Альберт (1999).
  9. ^ Дженсен и Тофт (2011), стр. 78: «Легко видеть, что col( G ) = Δ( G ) + 1 тогда и только тогда, когда G имеет Δ( G )-регулярный компонент». В обозначениях, используемых Дженсеном и Тофтом, col( G ) — это вырожденность плюс один, а Δ( G ) — максимальная степень вершины.
  10. ^ Матула (1968); Лик и Уайт (1970), Предложение 1, стр. 1084.
  11. ^ Хробак и Эппштейн (1991).
  12. ^ Сейдман (1983).
  13. ^ Боллобас (1984); Лучак (1991); Дороговцев, Гольцев и Мендес (2006).
  14. ^ Бадер и Хог (2003); Альтаф-Уль-Амин и др. (2003); Вухти и Алмаас (2005).
  15. ^ Гертлер и Патриньяни (2004); Альварес-Хамелин и др. (2006).
  16. ^ Гарсия-Альгарра и др. (2017).
  17. ^ Балог и др. (2012).
  18. ^ Киркпатрик и др. (2002).
  19. ^ Адлер (1991).
  20. ^ Хробак и Эппштейн (1991); Габоу и Вестерманн (1992); Венкатешваран (2004 г.); Асахиро и др. (2006); Ковалик (2006).
  21. ^ Дин, Хатчинсон и Шайнерман (1991).
  22. ^ Эрдеш и Хайнал (1966); Секерес и Уильф (1968).
  23. ^ Муди и Уайт (2003).
  24. ^ Робертсон и Сеймур (1984).
  25. ^ Берр и Эрдёш (1975).
  26. ^ Эппштейн, Д., Лёффлер, М. и Страш, Д. (2010). Перечисление всех максимальных клик в разреженных графах за почти оптимальное время. В O. Cheong, K.-Y. Chwa, & K. Park (ред.), Алгоритмы и вычисления (т. 6506, стр. 403–414). Берлин, Гейдельберг: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36

Ссылки