Виродженість (теорія графів)
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-ядро.
Вершина має ядерність якщо вершина належить -ядру, але не належить -ядру.
Поняття k-ядра введено для вивчення групування в соціальних мережах[15] та для опису розгортання випадкових графів[16][17][18]. Поняття також перенесено в біоінформатику[1][2] та візуалізацію мереж[19][20].
Алгоритми[ред. | ред. код]
Як описують Матула і Бек[8], можна знайти за лінійний час упорядкування вершин у скінченному графі G, що оптимізує число розфарбовування упорядкування, якщо для знаходження та видалення вершин найменшого степеня використовувати контейнерну чергу[en]. Виродженість тоді — це найбільший степінь будь-якої вершини на момент її видалення.
Детальніше, алгоритм працює так:
- Створюємо список виведення L.
- Для кожної вершини v графа G обчислюємо число dv — число сусідів вершини v, що ще не містяться в L. Спочатку ці числа просто рівні степеням вершин.
- Створюємо масив D, в якому D[i] містить список вершин v, які не входять до списку L, для яких dv = i.
- Присвоюємо k значення 0.
- Повторюємо n разів:
- переглядаємо елементи масиву 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 містить вершини в оптимальному порядку для числа розфарбовування. У графі 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 для кожного псевдолісу), так що найменший напівстепінь виходу такої орієнтації є псевдодеревністю, яка, знову ж, не перевищує виродженості[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].
Примітки[ред. | ред. код]
- ↑ а б Altaf-Ul-Amin, Nishikata, Koma, Miyasato и др., 2003.
- ↑ а б Wuchty, Almaas, 2005.
- ↑ Bader, Hogue, 2003.
- ↑ Freuder, 1982.
- ↑ Kirousis, Thilikos, 1996.
- ↑ а б в г д Erdős, Hajnal, 1966.
- ↑ Irani, 1994.
- ↑ а б Matula, Beck, 1983.
- ↑ а б Lick, White, 1970.
- ↑ Barabási, Albert, 1999.
- ↑ Єнсен і Тофт (Jensen, Toft, 2011), с. 78: «Легко бачити, що col(G) = Δ(G) + 1 тоді й лише тоді, коли G має Δ(G)-регулярну компоненту». В позначеннях Єнсена і Тофта col(G) дорівнює виродженню + 1, а Δ(G) дорівнює найбільшому степеню вершини.
- ↑ Matula, 1968.
- ↑ Lick, White, 1970, с. 1084 Proposition 1.
- ↑ а б Chrobak, Eppstein, 1991.
- ↑ Seidman, 1983.
- ↑ Bollobás, 1984.
- ↑ Łuczak, 1991.
- ↑ Dorogovtsev, Goltsev, Mendes, 2006.
- ↑ Gaertler, Patrignani, 2004.
- ↑ Alvarez-Hamelin, Dall'Asta, Barrat, Vespignani, 2005.
- ↑ Gabow, Westermann, 1992.
- ↑ Venkateswaran, 2004.
- ↑ Asahiro, Miyano, Ono, Zenmyo, 2006.
- ↑ Kowalik, 2006.
- ↑ Dean, Hutchinson, Scheinerman, 1991.
- ↑ Szekeres, Wilf, 1968.
- ↑ Moody, White, 2003.
- ↑ Robertson, Seymour, 1984.
- ↑ Burr, Erdős, 1975.
- ↑ 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. — 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:. — PMID 12525261 .
- Barabási Albert-László, Albert Réka. Emergence of scaling in random networks // Science. — 1999. — Т. 286, вип. 5439. — С. 509–512. — DOI:. — 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 // Theoretical Computer Science. — 1991. — Т. 86, вип. 2. — С. 243–266. — DOI:.
- Dean Alice M., Hutchinson Joan P., Scheinerman Edward R. On the thickness and arboricity of a graph // Journal of Combinatorial Theory. — 1991. — Т. 52, вип. 1. — С. 147–151. — (Series B). — DOI:.
- 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:. — 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:.
- Freuder Eugene C. A sufficient condition for backtrack-free search // Journal of the ACM. — 1982. — Т. 29, вип. 1. — С. 24–32. — DOI:.
- Gabow H. N., Westermann H. H. Forests, frames, and games: algorithms for matroid sums and applications // Algorithmica. — 1992. — Т. 7, вип. 1. — С. 465–497. — DOI:.
- 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 // Algorithmica. — 1994. — Т. 11, вип. 1. — С. 53–72. — DOI:.
- Jensen Tommy R., Toft Bjarne. Graph Coloring Problems. — John Wiley & Sons, 2011. — Т. 39. — (Wiley Series in Discrete Mathematics and Optimization) — ISBN 9781118030745.
- Kirousis L. M., Thilikos D. M. The linkage of a graph // SIAM Journal on Computing. — 1996. — Т. 25, вип. 3. — С. 626–647. — DOI:.
- 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:.
- Lee Choongbum. Ramsey numbers of degenerate graphs // Annals of Mathematics. — 2017. — Т. 185, вип. 3. — С. 791-829. — arXiv:1505.04773. — DOI:.
- Lick Don R., White Arthur T. k-degenerate graphs // Canadian Journal of Mathematics. — 1970. — Т. 22. — С. 1082–1096. — DOI:.
- Łuczak Tomasz. Size and connectivity of the k-core of a random graph // Discrete Mathematics. — 1991. — Т. 91, вип. 1. — С. 61–68. — DOI:.
- 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:.
- 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:.
- Moody James, White Douglas R. Structural cohesion and embeddedness: a hierarchical conception of social groups // American Sociological Review. — 2003. — Т. 68, вип. 1. — С. 1–25. — DOI:.
- Robertson Neil, Seymour Paul. Graph minors. III. Planar tree-width // Journal of Combinatorial Theory. — 1984. — Т. 36, вип. 1. — С. 49–64. — DOI:.
- Seidman Stephen B. Network structure and minimum degree // Social Networks. — 1983. — Т. 5, вип. 3. — С. 269–287. — DOI:.
- Szekeres George, Wilf Herbert S. An inequality for the chromatic number of a graph // Journal of Combinatorial Theory. — 1968. — Т. 4. — С. 1–3. — DOI:.
- Venkateswaran V. Minimizing maximum indegree // Discrete Applied Mathematics. — 2004. — Т. 143, вип. 1–3. — С. 374–378. — DOI:.
- Wuchty S., Almaas E. Peeling the yeast protein network // Proteomics. — 2005. — Т. 5, вип. 2. — С. 444–449. — DOI:. — PMID 15627958 .