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 -ядро.

Вершина ${\displaystyle u}$ имеет ядерность ${\displaystyle c}$ , если вершина принадлежит ${\displaystyle c}$ -ядру, но не принадлежит ${\displaystyle (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) рёбер, а потому имеет вершины со степенью, не превосходящей 2 k − 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 , являющееся вполне упорядоченным , в котором каждая вершина имеет менее α соседей среди предыдущих вершин в упорядочении. Неравенство между числом раскрашивания и хроматическим числом имеет место и для бесконечного случая. Эрдёш и Хайнал утверждали это, и на время публикации их работы факт был хорошо известен.

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

Примечания

Литература