2-вироджений граф — кожна вершина має не більше двох сусідів зліва, так що найправіша вершина будь-якого підграфа має степінь два і менше. Його 2-ядро, підграф, що залишається після видалення вершин зі степенем, меншим за два, виділено кольором.
k-ви́роджений граф — це неорієнтований граф, у якому кожен підграф має вершини зі степенем, що не перевищує k. Ви́родженість графа — це найменше значення k, для якого граф є k-виродженим. Виродженість графа відбиває, наскільки граф розріджений і (з точністю до сталого множника) відбиває інші заходи розрідженості, такі як деревність графа.
Виродженість відома також під назвою k-я́дерне число́[1][2][3], ширина́[4] і заче́плення[5], і, по суті, це те саме, що й число́ розфарбовува́ння[6] або число́ Секереша — Ві́лфа. k-вироджені графи називаються також k-індукти́вними гра́фами[7]. Виродженість графа можна обчислити за лінійний час за допомогою алгоритму, що послідовно видаляє вершини з найменшим степенем[8]. Компоненту зв'язності, що залишилася після видалення всіх вершин зі степенем, меншим від k називають k-ядро́м графа, і виродженість графа дорівнює найбільшому значенню k, для якого існує k-ядро.
Приклади
Будь-який ліс або має ізольовану вершину (без суміжних ребер), або листкову вершину (інцидентну рівно одному ребру), так що ліси і дерева є 1-виродженими графами.
Будь-який скінченний планарний граф має вершину степеня 5 або менше, тому будь-який планарний граф є 5-виродженим і виродженість будь-якого планарного графа не перевищує 5. Подібно до цього, виродженість будь-якого зовніпланарного графа не перевищує 2[9], а виродженість графів Аполлонія дорівнює 3.
Модель Барабаші — Альберт генерування випадковихбезмасштабних мереж[10] має як параметр число m, таке, що кожна вершина, додана до графа, пов'язана ребрами з m доданих раніше вершин. Звідси випливає, що будь-який підграф мережі, отриманий таким способом, має степінь вершин, не менший від m (це степінь останньої вершини, доданої до графа), так що мережі Барабаші — Альберт автоматично m -вироджені.
Будь-який k-регулярний граф має виродженість рівно k. Строгіше, виродженість графа дорівнює найбільшому степеню вершини тоді й лише тоді, коли принаймні одна з компонент зв'язності графа є регулярною і має степінь самого графа. Для решти графів виродженість строго менша від максимального степеня вершин графа[11].
Визначення
Число розфарбовування графа G ввели Ердеш і Хайнал[6] як найбільше , для якого існує впорядкування вершин графа G, за якого кожна вершина має менше сусідів, що передують вершині в порядку. Слід відрізняти це число від хроматичного числа графа G, найменшого числа кольорів, необхідних для розфарбування вершин, за якого ніякі дві суміжні вершини не пофарбовані в однаковий колір. Упорядкування, що визначає число розфарбовування, дає порядок розфарбовування вершин графа G в число кольорів, що дорівнює числу розфарбовування, але, в загальному випадку, хроматичне число може бути меншим від цього числа.
Лік та Вайт[9] визначили виродженість графа G як найменше число k, для якого будь-який породжений підграф графа G містить вершину з k і менше сусідами. Визначення не зміниться, якщо замість породжених підграфів брати довільні підграфи, оскільки непороджений підграф може мати степені вершин, що не перевищують степенів вершин породженого з тим самим набором вершин підграфа.
Два поняття, число розфарбовування та виродженість, еквівалентні — в будь-якому скінченному графі виродженість на одиницю менша від числа розфарбовування[12][13]. Якщо граф має упорядкування з числом розфарбовування , то в кожному підграфі H вершина, що належить H і є останньою в упорядкуванні, має не більше сусідів у 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-ядро.
Вершина має ядерність якщо вершина належить -ядру, але не належить -ядру.
Як описують Матула і Бек[8], можна знайти за лінійний час упорядкування вершин у скінченному графі G, що оптимізує число розфарбовування упорядкування, якщо для знаходження та видалення вершин найменшого степеня використовувати контейнерну чергу. Виродженість тоді — це найбільший степінь будь-якої вершини на момент її видалення.
Детальніше, алгоритм працює так:
Створюємо список виведення L.
Для кожної вершини v графа G обчислюємо число dv — число сусідів вершини v, що ще не містяться в L. Спочатку ці числа просто рівні степеням вершин.
Створюємо масив D, в якому D[i] містить список вершин v, які не входять до списку L, для яких dv = i.
переглядаємо елементи масиву 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 містить вершини в оптимальному порядку для числа розфарбовування. У графі Gi-ядра — це підсписки списку L, що складаються з вершин, доданих до L після того, як k вперше набуло значення, більшого або рівного i.
Ініціалізувати змінні L, dv, D і k можна легко за лінійний час. Знаходження чергової вершини, що видаляється, і перерахунок елементів 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-ядер поняття, яке ґрунтується на зв'язності вершин, вивчається в теорії соціальних мереж під назвою структурні зв'язки[en][27].
Якщо деревна ширина або шляхова ширина графа не перевищує k, то він є підграфом хордального графа, що має досконалий порядок виключення, за якого кожна вершина має не більше k попередніх сусідів. Таким чином, виродженість не перевищує деревної ширини та колійної ширини. Однак існують графи з обмеженою виродженістю та необмеженою деревною шириною, як, наприклад, решітки[28].
Гіпотеза Ердеша — Бура стосується зв'язку виродженості графа G і числа Рамсея графа G, найбільшого n, для якого будь-яке двоколірне розфарбування ребер повного графа з n вершинами повинне містити монохромну копію графа G. Конкретно, гіпотеза стверджує, що для будь-якого фіксованого значення k число Рамсея k-вироджених графів зростає лінійно від числа вершин графів[29]. Гіпотезу довів Лі[30].
Нескінченні графи
Хоча поняття виродженості та числа розфарбовування часто застосовують у контексті скінченних графів, початковою метою Ердеша та Хайнала[6] була теорія нескінченних графів. Число розфарбовування для нескінченного графа G можна визначити аналогічно визначенню для скінченних графів як найменше кардинальне число α, для якого існує впорядкування вершин графа G, що є цілком упорядкованим, у якому кожна вершина має менше α сусідів серед попередніх вершин в упорядкуванні. Нерівність між числом розфарбовування та хроматичним числом виконується і для нескінченного випадку. Ердеш і Хайнал[6] стверджували це, і на час публікації їхньої роботи факт був добре відомим.
↑Єнсен і Тофт (Jensen, Toft, 2011), с. 78: «Легко бачити, що col(G) = Δ(G) + 1 тоді й лише тоді, коли G має Δ(G)-регулярну компоненту». В позначеннях Єнсена і Тофта col(G) дорівнює виродженню + 1, а Δ(G) дорівнює найбільшому степеню вершини.
Alvarez-Hamelin José Ignacio, Dall'Asta Luca, Barrat Alain, Vespignani Alessandro.k-core decomposition: a tool for the visualization of large scale networks. — 2005. — arXiv:cs/0504107.
Asahiro Yuichi, Miyano Eiji, Ono Hirotaka, Zenmyo Kouhei. Graph orientation algorithms to minimize the maximum outdegree // CATS '06: Proceedings of the 12th Computing: The Australasian Theory Symposium. — Darlinghurst, Australia, Australia : Australian Computer Society, Inc, 2006. — С. 11–20. — ISBN 1-920682-33-3.
Bader Gary D., Hogue Christopher W. V. An automated method for finding molecular complexes in large protein interaction networks // BMC Bioinformatics. — 2003. — Т. 4, вип. 1. — DOI:10.1186/1471-2105-4-2. — PMID12525261 .
Bollobás Béla. The evolution of sparse graphs // Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf. in honor of Paul Erdős. — Academic Press, 1984. — С. 35–57.
Gabow H. N., Westermann H. H. Forests, frames, and games: algorithms for matroid sums and applications // Algorithmica. — 1992. — Т. 7, вип. 1. — С. 465–497. — DOI:10.1007/BF01758774.
Jensen Tommy R., Toft Bjarne. Graph Coloring Problems. — John Wiley & Sons, 2011. — Т. 39. — (Wiley Series in Discrete Mathematics and Optimization) — ISBN 9781118030745.
Kowalik Łukasz. Approximation scheme for lowest outdegree orientation and graph density measures // Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006). — Springer-Verlag, 2006. — Т. 4288. — С. 557–566. — DOI:10.1007/11940128_56.
Matula D. W. A min-max theorem for graphs with application to graph coloring (SIAM 1968 National Meeting) // SIAM Review. — 1968. — Т. 10, вип. 4. — С. 481–482. — DOI:10.1137/1010115.
Matula D. W., Beck L. L. Smallest-last ordering and clustering and graph coloring algorithms // Journal of the ACM. — 1983. — Т. 30, вип. 3. — С. 417–427. — DOI:10.1145/2402.322385.
