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

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

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

Виродженість відома також під назвою 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] як найбільше ${\displaystyle \kappa }$, для якого існує впорядкування вершин графа G, за якого кожна вершина має менше ${\displaystyle \kappa }$ сусідів, що передують вершині в порядку. Слід відрізняти це число від хроматичного числа графа G, найменшого числа кольорів, необхідних для розфарбування вершин, за якого ніякі дві суміжні вершини не пофарбовані в однаковий колір. Упорядкування, що визначає число розфарбовування, дає порядок розфарбовування вершин графа G в число кольорів, що дорівнює числу розфарбовування, але, в загальному випадку, хроматичне число може бути меншим від цього числа.

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

Два поняття, число розфарбовування та виродженість, еквівалентні — в будь-якому скінченному графі виродженість на одиницю менша від числа розфарбовування^[12][13]. Якщо граф має упорядкування з числом розфарбовування ${\displaystyle \kappa }$, то в кожному підграфі H вершина, що належить H і є останньою в упорядкуванні, має не більше ${\displaystyle \kappa -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-ядро.

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

Поняття k-ядра введено для вивчення групування в соціальних мережах^[15] та для опису розгортання випадкових графів^[16][17][18]. Поняття також перенесено в біоінформатику^[1][2] та візуалізацію мереж^[19][20].

Алгоритми

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

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

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

При завершенні алгоритму k містить виродженість графа G, а список L містить вершини в оптимальному порядку для числа розфарбовування. У графі G i-ядра — це підсписки списку L, що складаються з вершин, доданих до L після того, як k вперше набуло значення, більшого або рівного i.

Ініціалізувати змінні L, d_v, D і k можна легко за лінійний час. Знаходження чергової вершини, що видаляється, і перерахунок елементів D, що містять сусідів вершини v, займає час, пропорційний значенню d_v на цьому кроці, але сума таких значень дорівнює числу ребер графа, так що загальний час лінійний.

Зв'язок з іншими параметрами графа

Якщо граф 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] стверджували це, і на час публікації їхньої роботи факт був добре відомим.

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