|
Вырожденность (теория графов) 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-Ядраk-Ядро графа G — это максимальный связный подграф графа G, в котором все вершины имеют степень по меньшей мере k. Эквивалентно, это одна из связных компонент подграфа G, образованного последовательным удалением всех вершин со степенью, меньшей k. Если существует непустое k-ядро, ясно, что G имеет вырожденность, не меньшую k, а вырожденность графа G — это наибольшее число k, для которого G имеет k-ядро. Вершина имеет ядерность , если вершина принадлежит -ядру, но не принадлежит - ядру. Понятие k-ядра было введено для изучения группировки в социальных сетях[15] и для описания развёртывания случайных графов[16][17][18]. Понятие было также перенесено в биоинформатику[1][2] и визуализацию сетей[19][20]. АлгоритмыКак описывают Матула и Бек[8], можно найти за линейное время упорядочение вершин в конечном графе G, оптимизирующее число раскрашивания упорядочения, если использовать контейнерную очередь[англ.] для нахождения и удаления вершин наименьшей степени. Вырожденность тогда — это наибольшая степень любой вершины на момент её удаления. Более детально, алгоритм работает следующим образом:
При завершении алгоритма 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 для каждого псевдолеса), так что наименьшая полустепень исхода такой ориентации является псевдодревесностью, которая, снова, не превосходит вырожденности[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] утверждали это, и на время публикации их работы факт был хорошо известен. Вырождение случайных подмножеств бесконечных решёток изучается в теории с названием инициирующее просачивание[англ.]. Примечания
Литература
|
