Русская Википедия:Вырожденность (теория графов)
k-Вырожденный граф — это неориентированный граф, в котором каждый подграф имеет вершины со степенью, не превосходящей k. Вырожденность графа — это наименьшее значение k, для которого граф является k-вырожденным. Вырожденность графа отражает, насколько граф разрежен и (с точностью до постоянного множителя) отражает другие меры разреженности, такие как древесность графа.
Вырожденность известна также под именем k-ядерное числоШаблон:SfnШаблон:SfnШаблон:Sfn, ширинаШаблон:Sfn и зацеплениеШаблон:Sfn, и, по существу, это то же самое, что и число раскраскиШаблон:Sfn или число Секереша — Вилфа. k-Вырожденные графы называются также k-индуктивными графамиШаблон:Sfn. Вырожденность графа может быть вычислена за линейное время с помощью алгоритма, который последовательно удаляет вершины с минимальной степеньюШаблон:Sfn. Компонента связности, оставшаяся после удаления всех вершин со степенью , меньшей k, называется k-ядром графа, и вырожденность графа равна наибольшему значению k, для которого существует k-ядро.
Примеры
Любой лес либо имеет изолированную вершину (без смежных рёбер), либо листовую вершину (инцидентную в точности одному ребру), так что леса и деревья являются 1-вырожденными графами.
Любой конечный планарный граф имеет вершину степени пять или менее, так что любой планарный граф является 5-вырожденным и вырожденность любого планарного графа не превосходит пяти. Подобно этому, вырожденность любого внешнепланарного графа не превосходит двухШаблон:Sfn, а вырожденность графов Аполлония равна трём.
Модель Барабаши — Альберт генерации случайных безмасштабных сетейШаблон:Sfn имеет в качестве параметра число m, такое, что каждая вершина, добавленная к графу, связана рёбрами с m добавленных ранее вершин. Отсюда следует, что любой подграф сети, полученный таким способом, имеет степень вершин, не меньшую m (это степень последней вершины, добавленной в граф), так что сети Барабаши — Альберт автоматически m-вырожденные.
Любой k-регулярный граф имеет вырожденность в точности k. Более строго, вырожденность графа равна наибольшей степени вершины тогда и только тогда, когда по меньшей мере одна из компонент связности графа является регулярной и имеет степень самого графа. Для всех остальных графов вырожденность строго меньше наибольшей степени вершин графа[1]
Определения
Число раскрашивания графа G ввели Эрдёш и ХайналШаблон:Sfn как наибольшее κ, для которого существует упорядочение вершин графа G, при котором каждая вершина имеет меньше κ соседей, предшествующих вершине в порядке. Следует отличать это число от хроматического числа графа G, минимального числа цветов, необходимых для раскраски вершин, при которой никакие две смежные вершины не выкрашены в одинаковый цвет. Упорядочение, определяющее число раскрашивания, даёт порядок раскрашивания вершин графа G в число цветов, равное числу раскрашивания, но, в общем случае, хроматическое число может быть меньше этого числа.
Вырожденность графа G Лик и УайтШаблон:Sfn определили как наименьшее число k, для которого любой порождённый подграф графа G содержит вершину с k и менее соседями. Определение не изменится, если вместо порождённых подграфов брать произвольные подграфы, поскольку непорождённый подграф может иметь степени вершин, не превосходящие степеней вершин порождённого с тем же набором вершин подграфа.
Два понятия, число раскрашивания и вырожденность, эквивалентны — в любом конечном графе вырожденность на единицу меньше числа раскрашиванияШаблон:SfnШаблон:Sfn. Если граф имеет упорядочение с числом раскрашивания κ, то в каждом подграфе H вершина, принадлежащая H и являющаяся последней в упорядочении, имеет не более κ − 1 соседей в H. В другом направлении, если G равно k-вырожденности, то упорядочение с числом раскрашивания k + 1 можно получить путём последовательного нахождения вершины v с максимум k соседями, удаления вершины v из графа, упорядочения оставшихся вершин и добавления вершины v в конец порядка.
Третье эквивалентное определение k-вырожденности графа G (или что число раскрашивания не превосходит k + 1) — граф k-вырожден тогда и только тогда, когда рёбра графа G могут быть ориентированы с образованием направленного ациклического графа с полустепенью исхода, не превосходящей kШаблон:Sfn. Такая ориентация может быть получена путём ориентации каждого ребра в сторону более ранней из двух вершин ребра согласно упорядочению. В другом направлении, если задана ориентация с полуисходом выхода k, упорядочение с числом раскрашивания k + 1 может быть получено как топлогическое упорядочение ориентированного ациклического графа.
k-Ядра
k-Ядро графа G — это максимальный связный подграф графа G, в котором все вершины имеют степень по меньшей мере k. Эквивалентно, это одна из связных компонент подграфа G, образованного последовательным удалением всех вершин со степенью, меньшей k. Если существует непустое k-ядро, ясно, что G имеет вырожденность, не меньшую k, а вырожденность графа G — это наибольшее число k, для которого G имеет k-ядро.
Вершина <math>u</math> имеет ядерность <math>c</math>, если вершина принадлежит <math>c</math>-ядру, но не принадлежит <math>(c+1)</math>- ядру.
Понятие k-ядра было введено для изучения группировки в социальных сетяхШаблон:Sfn и для описания развёртывания случайных графовШаблон:SfnШаблон:SfnШаблон:Sfn. Понятие было также перенесено в биоинформатикуШаблон:SfnШаблон:Sfn и визуализацию сетейШаблон:SfnШаблон:Sfn.
Алгоритмы
Как описывают Матула и БекШаблон:Sfn, можно найти за линейное время упорядочение вершин в конечном графе G, оптимизирующее число раскрашивания упорядочения, если использовать Шаблон:Не переведено 5 для нахождения и удаления вершин наименьшей степени. Вырожденность тогда — это наибольшая степень любой вершины на момент её удаления.
Более детально, алгоритм работает следующим образом:
- Создаём выходной список L.
- Вычисляем число dv для любой вершины v графа G, число соседей вершины v, ещё не находящихся в L. Начально эти числа просто равны степеням вершин.
- Создаём массив D, в котором D[i] содержит список вершин v, не входящих в список L, для которых dv = i.
- Присваиваем k значение 0.
- Повторяем n раз:
- Просматриваем элементы массива D[0], D[1], ..., пока не найдём i, для которого D[i] не пусто.
- Присваиваем k максимальное из двух значений (k,i)
- Выбираем вершину v из D[i]. Добавляем v в начало очереди L и удаляем её из D[i].
- Для каждой вершины w, соседней v и не находящейся в L, вычитаем единицу из dw и переносим w в элемент массива D, который соответствует новому значению dw.
При завершении алгоритма k содержит вырожденность графа G, а список L содержит вершины в оптимальном порядке для числа раскрашивания. В графе G i-ядра — это подсписки списка L, состоящие из вершин, добавленных в L после того, как k первый раз принимает значение, большее или равное i.
Инициализация переменных L, dv, D и k может быть легко сделана за линейное время. Нахождение очередной удаляемой вершины v и пересчёт элементов D, содержащих соседей вершины v, занимает время, пропорциональное значению dv на этом шаге, но сумма таких значений равна числу рёбер графа, так что общее время линейно.
Связь с другими параметрами графа
Если граф G является ориентированным ацикличным с полустепенью исхода k, то его дуги могут быть разбиты на k лесов путём выбора одного леса для каждой исходящей дуги каждой вершины. Таким образом, древесность графа G не превосходит его вырожденности. В обратном направлении, граф с n вершинами, который можно разбить на k лесов, имеет не более k(n − 1) рёбер, а потому имеет вершины со степенью, не превосходящей 2k− 1. То есть вырожденность вдвое меньше древесности графа. Можно вычислить также за полиномиальное время ориентацию графа, минимизирующую степень полувыхода, не требуя ацикличности графа. Рёбра графа с такой ориентацией можно разбить тем же способом на k псевдолесов. И обратно, любое разбиение рёбер графа на k псевдолесов приводит к ориентации с наибольшей полустепенью исхода k (путём выбора ориентации с полустепенью выхода 1 для каждого псевдолеса), так что наименьшая полустепень исхода такой ориентации является псевдодревесностью, которая, снова, не превосходит вырожденностиШаблон:SfnШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn. Толщина также (с точностью до постоянного множителя) пропорциональна древесности, так что то же самое верно и для вырожденностиШаблон:Sfn.
k-Вырожденный граф имеет хроматическое число, не превосходящее k + 1. Это можно показать простой индукцией по числу вершин в точности как при доказательстве теоремы о шести красках для планарных графов. Поскольку хроматическое число является верхней границей порядка наибольшей клики, этот порядок не превосходит вырожденности плюс единица. При использовании алгоритма жадной раскраски на упорядочение с оптимальным числом раскрашивания, можно раскрасить k-вырожденный граф, используя не более k + 1 цветовШаблон:SfnШаблон:Sfn.
Вершинно k-связный граф — это граф, который нельзя разбить на несколько компонент путём удаления менее k вершин, или, эквивалентно, это граф, в котором каждая пара вершин может быть соединена k путями, не имеющими общих вершин. Поскольку в этих путях должны исходить эти две вершины через различные рёбра, вершинно k-связный граф должен иметь вырожденность по меньшей мере k. Понятие, близкое k-ядрам, но основывающееся на связности вершин, изучается в теории социальных сетей под названием Шаблон:Не переведено 5Шаблон:Sfn.
Если древесная ширина или путевая ширина графа не превосходит k, тогда он является подграфом хордального графа, имеющего совершенный порядок исключения, при котором каждая вершина имеет не более k предшествующих соседей. Таким образом, вырожденность не превосходит древесной ширины и путевой ширины. Однако существуют графы с ограниченной вырожденностью и неограниченной древесной шириной, как, например, решёткиШаблон:Sfn.
Гипотеза Эрдёша — Бура касается связи вырожденности графа G и числа Рамсея графа G, наибольшего n, для которого любая двухцветная раскраска рёбер полного графа с n вершинами должна содержать монохромную копию графа G. Конкретно, гипотеза утверждает, что для любого фиксированного значения k число Рамсея k-вырожденных графов растёт линейно от числа вершин графовШаблон:Sfn. Гипотезу доказал ЛиШаблон:Sfn.
Бесконечные графы
Хотя понятия вырожденности и числа раскрашивания часто подразумевают контекст конечных графов, начальной целью Эрдёша и ХайналаШаблон:Sfn была теория бесконечных графов. Для бесконечного графа G можно определить число раскрашивания аналогично определению для конечных графов как наименьшее кардинальное число α, для которого существует упорядочение вершин графа G, являющееся вполне упорядоченным, в котором каждая вершина имеет менее α соседей среди предыдущих вершин в упорядочении. Неравенство между числом раскрашивания и хроматическим числом имеет место и для бесконечного случая. Эрдёш и ХайналШаблон:Sfn утверждали это, и на время публикации их работы факт был хорошо известен.
Вырождение случайных подмножеств бесконечных решёток изучается в теории с названием Шаблон:Не переведено 5.
Примечания
Литература
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- ↑ Йенсен и Тофт Шаблон:Harv, p. 78: «Легко видеть, что col(G) = Δ(G) + 1 тогда и только тогда, когда G имеет Δ(G)-регулярную компоненту». В обозначениях Йенсена и Тофта col(G) равно вырождению + 1, а Δ(G) равно максимальной степени вершины.
