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

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

Вершина ${\displaystyle u}$ имеет ядерность ${\displaystyle c}$, если вершина принадлежит ${\displaystyle c}$-ядру, но не принадлежит ${\displaystyle (c+1)}$- ядру.

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

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

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

• Создаём выходной список 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 максимальное из двух значений (k,i)
  • Выбираем вершину v из D[i]. Добавляем v в начало очереди L и удаляем её из D[i].
  • Для каждой вершины w, соседней v и не находящейся в L, вычитаем единицу из d_w и переносим w в элемент массива D, который соответствует новому значению d_w.

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

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

Если граф 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-ядрам, но основывающееся на связности вершин, изучается в теории социальных сетей под названием структурные связи^{[англ.][27]}.

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

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

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

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