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

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

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

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

Приклади

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

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

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

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

Визначення

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

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

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

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

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

Алгоритми

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

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

• Створюємо список виведення 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 для кожного псевдолісу), так що найменший напівстепінь виходу такої орієнтації є псевдодеревністю, яка, знову ж, не перевищує виродженості. Товщина також (з точністю до сталого множника) пропорційна деревності, так що те саме істинне й для виродженості.

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

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

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

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

Нескінченні графи

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

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

Примітки

1. Altaf-Ul-Amin, Nishikata, Koma, Miyasato и др., 2003.
2. Wuchty, Almaas, 2005.
3. Bader, Hogue, 2003.
4. Freuder, 1982.
5. Kirousis, Thilikos, 1996.
6. Erdős, Hajnal, 1966.
7. Irani, 1994.
8. Matula, Beck, 1983.
9. Lick, White, 1970.
10. Barabási, Albert, 1999.
11. Єнсен і Тофт (Jensen, Toft, 2011), с. 78: «Легко бачити, що col(G) = Δ(G) + 1 тоді й лише тоді, коли G має Δ(G)-регулярну компоненту». В позначеннях Єнсена і Тофта col(G) дорівнює виродженню + 1, а Δ(G) дорівнює найбільшому степеню вершини.
12. Matula, 1968.
13. Lick, White, 1970, с. 1084 Proposition 1.
14. Chrobak, Eppstein, 1991.
15. Seidman, 1983.
16. Bollobás, 1984.
17. Łuczak, 1991.
18. Dorogovtsev, Goltsev, Mendes, 2006.
19. Gaertler, Patrignani, 2004.
20. Alvarez-Hamelin, Dall'Asta, Barrat, Vespignani, 2005.
21. Gabow, Westermann, 1992.
22. Venkateswaran, 2004.
23. Asahiro, Miyano, Ono, Zenmyo, 2006.
24. Kowalik, 2006.
25. Dean, Hutchinson, Scheinerman, 1991.
26. Szekeres, Wilf, 1968.
27. Moody, White, 2003.
28. Robertson, Seymour, 1984.
29. Burr, Erdős, 1975.
30. Lee, 2017.

Література

• Altaf-Ul-Amin M., Nishikata K., Koma T., Miyasato T., Shinbo Y., Arifuzzaman M., Wada C., Maeda M., Oshima T. Prediction of protein functions based on k-cores of protein-protein interaction networks and amino acid sequences // Genome Informatics. — 2003. — Т. 14. — С. 498–499.
• 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. — .
• Bader Gary D., Hogue Christopher W. V. An automated method for finding molecular complexes in large protein interaction networks // . — 2003. — Т. 4, вип. 1. — DOI:10.1186/1471-2105-4-2. — PMID 12525261 .
• Barabási Albert-László, Albert Réka. Emergence of scaling in random networks // Science. — 1999. — Т. 286, вип. 5439. — С. 509–512. — DOI:10.1126/science.286.5439.509. — PMID 10521342 . з джерела 17 квітня 2012.
• 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.
• Burr Stefan A., Erdős Paul. On the magnitude of generalized Ramsey numbers for graphs // Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. 1. — Amsterdam : North-Holland, 1975. — Т. 10. — С. 214–240. — (Colloq. Math. Soc. János Bolyai)
• Chrobak Marek, Eppstein David. Planar orientations with low out-degree and compaction of adjacency matrices // . — 1991. — Т. 86, вип. 2. — С. 243–266. — DOI:10.1016/0304-3975(91)90020-3.
• Dean Alice M., Hutchinson Joan P., Scheinerman Edward R. On the thickness and arboricity of a graph // . — 1991. — Т. 52, вип. 1. — С. 147–151. — (Series B). — DOI:10.1016/0095-8956(91)90100-X.
• Dorogovtsev S. N., Goltsev A. V., Mendes J. F. F. k-core organization of complex networks // Physical Review Letters. — 2006. — Т. 96, вип. 4. — С. 040601. — arXiv:cond-mat/0509102. — DOI:10.1103/PhysRevLett.96.040601. — PMID 16486798 .
• Erdős Paul, Hajnal András. On chromatic number of graphs and set-systems // Acta Mathematica Hungarica. — 1966. — Т. 17, вип. 1–2. — С. 61–99. — DOI:10.1007/BF02020444.
• Freuder Eugene C. A sufficient condition for backtrack-free search // . — 1982. — Т. 29, вип. 1. — С. 24–32. — DOI:10.1145/322290.322292.
• Gabow H. N., Westermann H. H. Forests, frames, and games: algorithms for matroid sums and applications // . — 1992. — Т. 7, вип. 1. — С. 465–497. — DOI:10.1007/BF01758774.
• Gaertler Marco, Patrignani Maurizio. Dynamic analysis of the autonomous system graph // Proc. 2nd International Workshop on Inter-Domain Performance and Simulation (IPS 2004). — 2004. — С. 13–24.
• Irani Sandy. Coloring inductive graphs on-line // . — 1994. — Т. 11, вип. 1. — С. 53–72. — DOI:10.1007/BF01294263.
• Jensen Tommy R., Toft Bjarne. Graph Coloring Problems. — John Wiley & Sons, 2011. — Т. 39. — (Wiley Series in Discrete Mathematics and Optimization) — .
• Kirousis L. M., Thilikos D. M. The linkage of a graph // . — 1996. — Т. 25, вип. 3. — С. 626–647. — DOI:10.1137/S0097539793255709.
• 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.
• Lee Choongbum. Ramsey numbers of degenerate graphs // Annals of Mathematics. — 2017. — Т. 185, вип. 3. — С. 791-829. — arXiv:1505.04773. — DOI:10.4007/annals.2017.185.3.2.
• Lick Don R., White Arthur T. k-degenerate graphs // . — 1970. — Т. 22. — С. 1082–1096. — DOI:10.4153/CJM-1970-125-1.
• Łuczak Tomasz. Size and connectivity of the k-core of a random graph // . — 1991. — Т. 91, вип. 1. — С. 61–68. — DOI:10.1016/0012-365X(91)90162-U.
• Matula D. W. A min-max theorem for graphs with application to graph coloring (SIAM 1968 National Meeting) // . — 1968. — Т. 10, вип. 4. — С. 481–482. — DOI:10.1137/1010115.
• Matula D. W., Beck L. L. Smallest-last ordering and clustering and graph coloring algorithms // . — 1983. — Т. 30, вип. 3. — С. 417–427. — DOI:10.1145/2402.322385.
• Moody James, White Douglas R. Structural cohesion and embeddedness: a hierarchical conception of social groups // . — 2003. — Т. 68, вип. 1. — С. 1–25. — DOI:10.2307/3088904.
• Robertson Neil, Seymour Paul. Graph minors. III. Planar tree-width // . — 1984. — Т. 36, вип. 1. — С. 49–64. — DOI:10.1016/0095-8956(84)90013-3.
• Seidman Stephen B. Network structure and minimum degree // . — 1983. — Т. 5, вип. 3. — С. 269–287. — DOI:10.1016/0378-8733(83)90028-X.
• Szekeres George, Wilf Herbert S. An inequality for the chromatic number of a graph // . — 1968. — Т. 4. — С. 1–3. — DOI:10.1016/S0021-9800(68)80081-X.
• Venkateswaran V. Minimizing maximum indegree // . — 2004. — Т. 143, вип. 1–3. — С. 374–378. — DOI:10.1016/j.dam.2003.07.007.
• Wuchty S., Almaas E. Peeling the yeast protein network // . — 2005. — Т. 5, вип. 2. — С. 444–449. — DOI:10.1002/pmic.200400962. — PMID 15627958 .