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

В теории графов 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 -ядра

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

Вершина имеет сердцевинность , если она принадлежит -ядру , но не принадлежит какому-либо -ядру. $и$ $с$ $с$ $(c+1)$

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

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

Алгоритмы

Матула и Бек (1983) обрисовали алгоритм для получения порядка вырождения графа с набором вершин $V$ и набором ребер $E$ во времени и словах пространства путем сохранения вершин в очереди сегментов с индексацией по степени и многократного удаления вершины с наименьшим числом. степень. Вырождение $k$ определяется наивысшей степенью любой вершины на момент ее удаления. $G=(V,E)$ ${\mathcal {O}}(\vert V\vert +\vert E\vert)$ ${\mathcal {O}}(\vert V\vert)$

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

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

В конце алгоритма любая вершина будет иметь не более $k$ ребер, ведущих в вершины . $l$ - ядра графа $G$ — это подграфы , порожденные вершинами , где $i$ — первая вершина, имеющая степень на момент ее добавления в $L.$ $L[я]$ $L[1,\ldots,i-1]$ $H_{l}\subset G$ $L[1,\ldots,i]$ $\geq 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] поэтому говорят, что класс графов с ограниченным вырождением имеет мало клик. $п$ $d$ ${\textstyle (nd)3^{d/3}}$ $d\equiv 0\mod 3$ $n\geq d+3$

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

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

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

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

Примечания

^ Бадер и Хог (2003).
^ Фрейдер (1982).
^ Кирусис и Тиликос (1996).
^ Эрдеш и Хайнал (1966).
^ Ирани (1994).
^ Матула и Бек (1983).
^ Лик и Уайт (1970).
^ Барабаси и Альберт (1999).
^ Дженсен и Тофт (2011), с. 78: «Легко видеть, что col( G ) = ∆( G ) + 1 тогда и только тогда, когда G имеет ∆( G )-регулярную компоненту». В обозначениях, используемых Дженсеном и Тофтом, col( G ) — это вырождение плюс один, а Δ( G ) — максимальная степень вершины.
^ Матула (1968); Lick & White (1970), Предложение 1, стр. 1084.
^ Хробак и Эппштейн (1991).
^ Зейдман (1983).
^ Боллобас (1984); Лучак (1991); Дороговцев, Гольцев и Мендес (2006).
^ Бадер и Хог (2003); Альтаф-Уль-Амин и др. (2003); Вухти и Алмаас (2005).
^ Гертлер и Патриньяни (2004); Альварес-Хамелин и др. (2006).
^ Гарсия-Альгарра и др. (2017).
^ Балог и др. (2012).
^ Киркпатрик и др. (2002).
^ Адлер (1991).
^ Хробак и Эппштейн (1991); Габоу и Вестерманн (1992); Венкатешваран (2004 г.); Асахиро и др. (2006); Ковалик (2006).
^ Дин, Хатчинсон и Шайнерман (1991).
^ Эрдеш и Хайнал (1966); Секерес и Уильф (1968).
^ Муди и Уайт (2003).
^ Робертсон и Сеймур (1984).
^ Берр и Эрдеш (1975).
^ Эппштейн Д., Леффлер М. и Страш Д. (2010). Перечисление всех максимальных клик в разреженных графах за время, близкое к оптимальному. У О. Чеонга, К.-Ю. Чва и К. Парк (ред.), Алгоритмы и вычисления (том 6506, стр. 403–414). Берлин, Гейдельберг: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36