 2-вироджений граф — кожна вершина має не більше двох сусідів зліва, так що найправіша вершина будь-якого підграфа має степінь два і менше. Його 2-ядро, підграф, що залишається після видалення вершин зі степенем, меншим за два, виділено кольором.
k-ви́роджений граф — це неорієнтований граф, у якому кожен підграф має вершини зі степенем, що не перевищує k. Ви́родженість графа — це найменше значення k, для якого граф є k-виродженим. Виродженість графа відбиває, наскільки граф розріджений і (з точністю до сталого множника) відбиває інші заходи розрідженості, такі як деревність графа.

Виродженість відома також під назвою k-я́дерне число́, ширина́ і заче́плення, і, по суті, це те саме, що й число́ розфарбовува́ння або число́ Секереша — Ві́лфа. k-вироджені графи називаються також k-індукти́вними гра́фами. Виродженість графа можна обчислити за лінійний час за допомогою алгоритму, що послідовно видаляє вершини з найменшим степенем. Компоненту зв'язності, що залишилася після видалення всіх вершин зі степенем, меншим від k називають k-ядро́м графа, і виродженість графа дорівнює найбільшому значенню k, для якого існує k-ядро.

Приклади
Будь-який ліс або має ізольовану вершину (без суміжних ребер), або листкову вершину (інцидентну рівно одному ребру), так що ліси і дерева є 1-виродженими графами.

Будь-який скінченний планарний граф має вершину степеня 5 або менше, тому будь-який планарний граф є 5-виродженим і виродженість будь-якого планарного графа не перевищує 5. Подібно до цього, виродженість будь-якого зовніпланарного графа не перевищує 2, а виродженість графів Аполлонія дорівнює 3.

Модель Барабаші — Альберт генерування випадкових безмасштабних мереж має як параметр число m, таке, що кожна вершина, додана до графа, пов'язана ребрами з m доданих раніше вершин. Звідси випливає, що будь-який підграф мережі, отриманий таким способом, має степінь вершин, не менший від m (це степінь останньої вершини, доданої до графа), так що мережі Барабаші — Альберт автоматично m -вироджені.

Будь-який k-регулярний граф має виродженість рівно k. Строгіше, виродженість графа дорівнює найбільшому степеню вершини тоді й лише тоді, коли принаймні одна з компонент зв'язності графа є регулярною і має степінь самого графа. Для решти графів виродженість строго менша від максимального степеня вершин графа.

Визначення
Число розфарбовування графа G ввели Ердеш і Хайнал як найбільше , для якого існує впорядкування вершин графа G, за якого кожна вершина має менше  сусідів, що передують вершині в порядку. Слід відрізняти це число від хроматичного числа графа G, найменшого числа кольорів, необхідних для розфарбування вершин, за якого ніякі дві суміжні вершини не пофарбовані в однаковий колір. Упорядкування, що визначає число розфарбовування, дає порядок розфарбовування вершин графа G в число кольорів, що дорівнює числу розфарбовування, але, в загальному випадку, хроматичне число може бути меншим від цього числа.

Лік та Вайт визначили виродженість графа G як найменше число k, для якого будь-який породжений підграф графа G містить вершину з k і менше сусідами. Визначення не зміниться, якщо замість породжених підграфів брати довільні підграфи, оскільки непороджений підграф може мати степені вершин, що не перевищують степенів вершин породженого з тим самим набором вершин підграфа.

Два поняття, число розфарбовування та виродженість, еквівалентні — в будь-якому скінченному графі виродженість на одиницю менша від числа розфарбовування. Якщо граф має упорядкування з числом розфарбовування , то в кожному підграфі H вершина, що належить H і є останньою в упорядкуванні, має не більше  сусідів у H. З іншого боку, якщо G дорівнює k-виродженості, то впорядкування з числом розфарбовування k + 1 можна отримати послідовним знаходженням вершини v з максимум k сусідами, видаленням вершини v з графа, впорядкуванням решти вершин і додаванням вершини v в кінець порядку.

Третє еквівалентне визначення k-виродженості графа G (або що число розфарбовування не перевищує k + 1) — граф k-вироджений тоді й лише тоді, коли ребра графа G можна зорієнтувати з утворенням спрямованого ациклічного графа з напівстепенем виходу, що не перевищує k. Таку орієнтацію можна отримати орієнтуванням кожного ребра в бік ранішої з двох вершин ребра в упорядкуванні. З іншого боку, якщо задано орієнтацію з напівстепенем виходу k, упорядкування з числом розфарбовування k + 1 можна отримати як топлогічне впорядкування орієнтованого ациклічного графа.

k-Ядра
k-Ядро графа G — це найбільший зв'язний підграф графа G, в якому всі вершини мають степінь принаймні k. Еквівалентно, це одна зі зв'язних компонент підграфа G, утвореного послідовним видаленням усіх вершин зі степенем, меншим від k. Якщо існує непорожнє k-ядро, ясно, що G має виродженість, не меншу від k, а виродженість графа G — це найбільше число k, для якого G має k-ядро.

Вершина  має ядерність  якщо вершина належить -ядру, але не належить -ядру.

Поняття k-ядра введено для вивчення групування в соціальних мережах та для опису розгортання випадкових графів. Поняття також перенесено в біоінформатику та візуалізацію мереж.

Алгоритми
Як описують Матула і Бек, можна знайти за лінійний час упорядкування вершин у скінченному графі G, що оптимізує число розфарбовування упорядкування, якщо для знаходження та видалення вершин найменшого степеня використовувати . Виродженість тоді — це найбільший степінь будь-якої вершини на момент її видалення.

Детальніше, алгоритм працює так:

* Створюємо список виведення L.
* Для кожної вершини v графа G обчислюємо число dv — число сусідів вершини v, що ще не містяться в L. Спочатку ці числа просто рівні степеням вершин.
* Створюємо масив D, в якому Di містить список вершин v, які не входять до списку L, для яких dv = i.
* Присвоюємо k значення 0.
* Повторюємо n разів:
** переглядаємо елементи масиву D 0, D 1, …, доки знайдемо i, якого Di не порожнє;
** присвоюємо k більше з двох значень (k,i);
** вибираємо вершину v з Di. Додаємо v на початок черги L і видаляємо її з Di.
** Для кожної вершини w, яка сусідня v і не міститься в L, віднімаємо одиницю від dw і переносимо w в елемент масиву D, який відповідає новому значенню dw.

При завершенні алгоритму k містить виродженість графа G, а список L містить вершини в оптимальному порядку для числа розфарбовування. У графі G i-ядра — це підсписки списку 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 для кожного псевдолісу), так що найменший напівстепінь виходу такої орієнтації є псевдодеревністю, яка, знову ж, не перевищує виродженості. Товщина також (з точністю до сталого множника) пропорційна деревності, так що те саме істинне й для виродженості.

k-Вироджений граф має хроматичне число, що не перевищує k + 1. Це можна показати простою індукцією за кількістю вершин, так само, як при доведенні теореми про шість фарб для планарних графів. Оскільки хроматичне число є верхньою межею порядку найбільшої кліки, цей порядок не перевищує виродженості плюс одиниця. Скориставшись алгоритмом жадібного розфарбування для порядку з оптимальним числом розфарбовування, можна розфарбувати k-вироджений граф, використавши не більше k + 1 кольору.

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

Якщо деревна ширина або шляхова ширина графа не перевищує k, то він є підграфом хордального графа, що має досконалий порядок виключення, за якого кожна вершина має не більше k попередніх сусідів. Таким чином, виродженість не перевищує деревної ширини та колійної ширини. Однак існують графи з обмеженою виродженістю та необмеженою деревною шириною, як, наприклад, решітки.

Гіпотеза Ердеша — Бура стосується зв'язку виродженості графа G і числа Рамсея графа G, найбільшого n, для якого будь-яке двоколірне розфарбування ребер повного графа з n вершинами повинне містити монохромну копію графа G. Конкретно, гіпотеза стверджує, що для будь-якого фіксованого значення k число Рамсея k-вироджених графів зростає лінійно від числа вершин графів. Гіпотезу довів Лі.

Нескінченні графи
Хоча поняття виродженості та числа розфарбовування часто застосовують у контексті скінченних графів, початковою метою Ердеша та Хайнала була теорія нескінченних графів. Число розфарбовування для нескінченного графа G можна визначити аналогічно визначенню для скінченних графів як найменше кардинальне число α, для якого існує впорядкування вершин графа G, що є цілком упорядкованим, у якому кожна вершина має менше α сусідів серед попередніх вершин в упорядкуванні. Нерівність між числом розфарбовування та хроматичним числом виконується і для нескінченного випадку. Ердеш і Хайнал стверджували це, і на час публікації їхньої роботи факт був добре відомим.

Виродження випадкових підмножин нескінченних ґраток вивчається під назвою .

Примітки


Література

* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 


