Вырождение (теория графов) - Degeneracy (graph theory)

2-вырожденный граф: каждая вершина имеет не более двух соседей слева, поэтому самая правая вершина любого подграфа имеет степень не более двух. Его 2-ядерный подграф, оставшийся после многократного удаления вершин степени меньше двух, закрашен.

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

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

Примеры

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

Каждый конечный планарный граф имеет вершину пятой или меньшей степени; следовательно, каждый планарный граф является 5-вырожденным, а вырожденность любого плоского графа не превосходит пяти. Точно так же каждый внешнепланарный граф имеет вырождение не более двух, а аполлонические сети имеют вырождение три.

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

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

Определения и эквиваленты

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

Вырождение графа G была определена Lick & White (1970) в качестве наименьшего к таким , что каждый индуцированный подграф из G содержит вершину с к или меньшим числом соседей. Определение было бы таким же, если бы произвольные подграфы разрешены вместо индуцированных подграфов, поскольку неиндуцированный подграф может иметь только степени вершин, которые меньше или равны степеням вершин в подграфе, индуцированном тем же множеством вершин.

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

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

k -Ядра

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

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

Концепция k- ядра была введена для изучения кластерной структуры социальных сетей и описания эволюции случайных графов . Он также применялся в биоинформатике , визуализации сетей , структуре Интернета, распространении экономических кризисов, выявлении влиятельных распространителей, структуре коры головного мозга или устойчивости сетей в экологии . Также были разработаны расширения k- ядерных структур в взвешенных сетях. Обзор темы, охватывающий основные концепции, важные алгоритмические методы, а также некоторые прикладные области, можно найти в Malliaros et al. (2019) .

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

Алгоритмы

Как описывают Матула и Бек (1983) , можно найти порядок вершин конечного графа G, который оптимизирует число раскраски порядка за линейное время , используя очередь ведра для многократного поиска и удаления вершины наименьшей степени. . Тогда вырожденность - это наивысшая степень любой вершины на момент ее удаления. Пусть n количество узлов в Графике.

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

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

В конце алгоритма k содержит вырождение G, а L содержит список вершин в оптимальном порядке для числа раскраски. В I -cores из G являются префиксами L , состоящим из вершин , добавленных к L после того, как к первому принимает большее значение , чем или равен  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 для каждого псевдолеса) , поэтому минимальная степень такой ориентации - это псевдоарборичность , которая опять же не более чем равна вырождению. Толщина также находится в постоянном факторе arboricity, а следовательно , и вырождения.

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

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

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

Гипотеза Барр-Эрдеш относится вырождение граф G к числу Ramsey из G , по меньшей мере п таким образом, что любые два-краев окраска из п -vertex полного граф должен содержать монохроматический копию G . В частности, гипотеза состоит в том, что для любого фиксированного значения k число Рамсея k -вырожденных графов линейно растет с увеличением числа вершин графов. Гипотеза была доказана Ли (2017) .

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

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

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

Смотрите также

• Теория графов
• Сетевая наука
• Теория перколяции
• Структура ядро ​​– периферия
• Гипотеза Сереседы

Примечания

использованная литература