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

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

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

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

Примеры

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

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

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

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

Определения

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

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

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

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

k-Ядра

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

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

Понятие k-ядра было введено для изучения группировки в социальных сетях и для описания развёртывания случайных графов. Понятие было также перенесено в биоинформатику и визуализацию сетей.

Алгоритмы

Как описывают Матула и Бек, можно найти за линейное время упорядочение вершин в конечном графе 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 для каждого псевдолеса), так что наименьшая полустепень исхода такой ориентации является псевдодревесностью, которая, снова, не превосходит вырожденности. Толщина также (с точностью до постоянного множителя) пропорциональна древесности, так что то же самое верно и для вырожденности.

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

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

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

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

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

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

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