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

«K-ядро» перенаправляется сюда. Ядро . графа — это другая концепция

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

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

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

Примеры

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

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

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

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

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

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

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

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

Третья эквивалентная формулировка состоит в том, что G является k -вырожденным (или имеет число раскраски не более k + 1) тогда и только тогда, когда ребра 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 -ядра было введено для изучения структуры кластеризации социальных сетей. и описать эволюцию случайных графов . Он также применяется в биоинформатике . сетевая визуализация , и устойчивость сетей в экологии . Обзор темы, охватывающий основные концепции, важные алгоритмические методы, а также некоторые области применения, можно найти в Malliaros et al. (2019) .

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

Алгоритмы

Матула и Бек (1983) описывают алгоритм определения порядка вырождения графа. $G=(V,E)$ с набором вершин V и набором ребер E в ${\mathcal {O}}(\vert V\vert +\vert E\vert )$ время и ${\mathcal {O}}(\vert V\vert )$ слов пространства, сохраняя вершины в очереди сегментов с индексом по степени и многократно удаляя вершину с наименьшей степенью. Вырождение k определяется наивысшей степенью любой вершины на момент ее удаления.

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

• Инициализируйте выходной список 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 .

В конце алгоритма любая вершина $L[i]$ будет иметь не более k ребер, ведущих в вершины $L[1,\ldots ,i-1]$. -ядра l группы G — это подграфы $H_{l}\subset G$ которые индуцированы вершинами $L[1,\ldots ,i]$, где i — первая вершина степени $\geq l$ в то время, когда он добавляется к L .

Связь с другими параметрами графика

Если граф 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 -вырожденных графов растет линейно с количеством вершин графов. Гипотезу доказал Ли (2017) .

Любой $n$-вершинный граф с вырождением $d$ имеет не более ${\textstyle (n-d)3^{d/3}}$ максимальные клики всякий раз, когда $d\equiv 0\mod 3$ и $n\geq d+3$, поэтому говорят, что класс графов с ограниченным вырождением имеет мало клик.

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

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

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

См. также

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

Ссылки

• Адлер, Джоан (1991), «Перколяция начальной загрузки», Physica A: Статистическая механика и ее приложения , 171 (3): 453–470, Бибкод : 1991PhyA..171..453A , doi : 10.1016/0378-4371(91) 90295-н
• Альтаф-Уль-Амин, М.; Нишиката, К.; Кома, Т.; Миясато, Т.; Шинбо, Ю.; Арифуззаман, М.; Вада, К.; Маэда, М.; Осима, Т. (2003), «Прогнозирование функций белка на основе k -ядер сетей белок-белкового взаимодействия и аминокислотных последовательностей» (PDF) , Genome Informatics , 14 : 498–499, заархивировано из оригинала (PDF) на сайте 27 сентября 2007 г.
• Альварес-Амелен, Хосе Игнасио; Далл'Аста, Лука; Баррат, Ален; Веспиньяни, Алессандро (2006), « К -ядерная декомпозиция: инструмент для визуализации крупномасштабных сетей», в Вайсе, Яир; Шёлкопф, Бернхард; Платт, Джон (ред.), Достижения в области нейронных систем обработки информации 18: Материалы конференции 2005 г. , том. 18, MIT Press, с. 41, arXiv : cs/0504107 , Bibcode : 2005cs........4107A , ISBN  0262232537
• Асахиро, Юичи; Мияно, Эйдзи; Оно, Хиротака; Зенмио, Кохей (2006), «Алгоритмы ориентации графа для минимизации максимальной исходящей степени», CATS '06: Материалы 12-го компьютерного симпозиума: Австралазийский теоретический симпозиум , Дарлингхерст, Австралия, Австралия: Австралийское компьютерное общество, Inc., стр. 11– 20, ISBN  1-920682-33-3
• Бадер, Гэри Д.; Хог, Кристофер В.В. (2003), «Автоматизированный метод поиска молекулярных комплексов в больших сетях взаимодействия белков», BMC Bioinformatics , 4 (1): 2, doi : 10.1186/1471-2105-4-2 , PMC   149346 , PMID   12525261
• Балог, Йожеф; Боллобас, Бела ; Думинил-Копен, Гюго; Моррис, Роберт (2012), «Резкий порог бутстреп-перколяции во всех измерениях», Transactions of the American Mathematical Society , 364 (5): 2667–2701, arXiv : 1010.3326 , doi : 10.1090/S0002-9947-2011-05552 -2 , МР   2888224 , S2CID   2708046
• Барабаши, Альберт-Ласло ; Альберт, Река (1999), «Появление масштабирования в случайных сетях» (PDF) , Science , 286 (5439): 509–512, arXiv : cond-mat/9910332 , Bibcode : 1999Sci...286..509B , doi : 10.1126/science.286.5439.509 , PMID   10521342 , S2CID   524106 , заархивировано из оригинала (PDF) 11 ноября 2006 г.
• Боллобас, Бела (1984), «Эволюция разреженных графов», Теория графов и комбинаторика, Proc. Кембриджская комбинаторная конференция. в честь Пола Эрдеша , Academic Press, стр. 35–57.
• Берр, Стефан А .; Эрдеш, Пол (1975), «О величине обобщенных чисел Рамсея для графов», Бесконечные и конечные множества (Colloq., Keszthely, 1973; посвящено П. Эрдешу в день его 60-летия), Том 1 (PDF) , Colloq. . Математика. Сок. Янош Бояи, том. 10, Амстердам: Северная Голландия, стр. 214–240, МР   0371701
• Хробак, Марек; Эппштейн, Дэвид (1991), «Плоские ориентации с низкой исходящей степенью и уплотнением матриц смежности» (PDF) , Theoretical Computer Science , 86 (2): 243–266, doi : 10.1016/0304-3975(91)90020- 3
• Дин, Элис М.; Хатчинсон, Джоан П .; Шайнерман, Эдвард Р. (1991), «О толщине и древесности графа», Журнал комбинаторной теории , серия B, 52 (1): 147–151, doi : 10.1016/0095-8956(91)90100-X , МР   1109429
• Дороговцев С.Н.; Гольцев А.В.; Мендес, JFF (2006), « K -ядерная организация сложных сетей», Physical Review Letters , 96 (4): 040601, arXiv : cond-mat/0509102 , Bibcode : 2006PhRvL..96d0601D , doi : 10.1103/PhysRevLett.96.040601 , PMID   16486798 , S2CID   2035
• Эрдос, Пол ; Хайнал, Андраш (1966), «О хроматическом числе графов и системах множеств» (PDF) , Acta Mathematica Hungarica , 17 (1–2): 61–99, doi : 10.1007/BF02020444 , MR   0193025
• Фрейдер, Юджин К. (1982), «Достаточное условие для поиска без возврата», Журнал ACM , 29 (1): 24–32, doi : 10.1145/322290.322292 , S2CID   8624975
• Габоу, Гонконг ; Вестерманн, Х.Х. (1992), «Леса, фреймы и игры: алгоритмы матроидных сумм и приложений», Algorithmica , 7 (1): 465–497, doi : 10.1007/BF01758774 , S2CID   40358357
• Гертлер, Марко; Патриньяни, Маурицио (2004), «Динамический анализ графа автономной системы», Proc. 2-й международный семинар по междоменной производительности и моделированию (IPS 2004) , стр. 13–24, CiteSeerX   10.1.1.81.6841
• Гарсиа-Альгарра, Хавьер; пастор Хуан Мануэль; Ириондо, Хосе Мария; Галеано, Хавьер (2017), «Рейтинг критических видов для сохранения функциональности мутуалистических сетей с использованием k -ядерной декомпозиции», PeerJ , 5 : e3321, doi : 10.7717/peerj.3321 , PMC   5438587 , PMID   28533969
• Ирани, Сэнди (1994), «Раскраска индуктивных графов онлайн», Algorithmica , 11 (1): 53–72, doi : 10.1007/BF01294263 , S2CID   181800
• Дженсен, Томми Р.; Тофт, Бьерн (2011), Проблемы раскраски графов , Ряды Уайли по дискретной математике и оптимизации, том. 39, Джон Уайли и сыновья, ISBN  9781118030745
• Киркпатрик, Скотт; Вилке, Винфрид В.; Гарнер, Роберт Б.; Хьюлс, Харальд (2002), «Просачивание в плотных массивах хранения», Physica A: Статистическая механика и ее приложения , 314 (1–4): 220–229, Бибкод : 2002PhyA..314..220K , doi : 10.1016/S0378 -4371(02)01153-6 , МР   1961703
• Кирусис, Л.М.; Тиликос, Д.М. (1996), «Связь графа» (PDF) , SIAM Journal on Computing , 25 (3): 626–647, doi : 10.1137/S0097539793255709 , заархивировано из оригинала (PDF) 07.2011 г. 21
• Ковалик, Лукаш (2006), «Схема аппроксимации для мер ориентации наименьших исходящих степеней и плотности графов», Труды 17-го Международного симпозиума по алгоритмам и вычислениям (ISAAC 2006) , Конспекты лекций по информатике, 4288 , Springer-Verlag: 557–566 , doi : 10.1007/11940128_56 , ISBN  978-3-540-49694-6
• Ли, Чунгбум (2017), «Числа Рэмси вырожденных графов», Annals of Mathematics , 185 (3): 791–829, arXiv : 1505.04773 , doi : 10.4007/annals.2017.185.3.2 , S2CID   7974973
• Лик, Дон Р.; Уайт, Артур Т. (1970), « k -вырожденные графы», Canadian Journal of Mathematics , 22 (5): 1082–1096, doi : 10.4153/CJM-1970-125-1
• Лучак, Томаш (1991), «Размер и связность k -ядра случайного графа» (PDF) , Discrete Mathematics , 91 (1): 61–68, doi : 10.1016/0012-365X(91)90162-U
• Маллиарос, Фрагкискос Д.; Гиацидис, Христос; Пападопулос, Апостолос Н.; Вазиргианнис, Михалис (2019), «Основная декомпозиция сетей: теория, алгоритмы и приложения» (PDF) , The VLDB Journal , 29 : 61–92, doi : 10.1007/s00778-019-00587-4 , S2CID   85519668
• Матула, Дэвид В. (1968), «Теорема о мин-максе для графов с применением к раскраске графов», Национальное собрание SIAM 1968 г., SIAM Review , 10 (4): 481–482, doi : 10.1137/1010115
• Матула, Дэвид В .; Бек, Л.Л. (1983), «Алгоритмы упорядочения, кластеризации и раскраски графов наименьшего прошлого», Журнал ACM , 30 (3): 417–427, doi : 10.1145/2402.322385 , MR   0709826 , S2CID   4417741
• Муди, Джеймс; Уайт, Дуглас Р. (2003), «Структурная сплоченность и включенность: иерархическая концепция социальных групп» , American Sociological Review , 68 (1): 1–25, doi : 10.2307/3088904 , JSTOR   3088904
• Робертсон, Нил ; Сеймур, Пол (1984), «Минорные графы. III. Ширина плоского дерева», Журнал комбинаторной теории , серия B, 36 (1): 49–64, doi : 10.1016/0095-8956(84)90013-3
• Зейдман, Стивен Б. (1983), «Структура сети и минимальная степень», Социальные сети , 5 (3): 269–287, doi : 10.1016/0378-8733(83)90028-X
• Секерес, Джордж ; Уилф, Герберт С. (1968), «Неравенство для хроматического числа графа», Журнал комбинаторной теории , 4 : 1–3, doi : 10.1016/S0021-9800(68)80081-X
• Венкатешваран, В. (2004), «Минимизация максимального угла наклона», Discrete Applied Mathematics , 143 (1–3): 374–378, doi : 10.1016/j.dam.2003.07.007
• Вухти, С.; Алмаас, Э. (2005), «Очистка белковой сети дрожжей», Proteomics , 5 (2): 444–449, doi : 10.1002/pmic.200400962 , PMID   15627958 , S2CID   17659720