Дегенерисани графови

2-дегенерисан граф:сваки чвор има највише два суседа са своје леве стране, тако да скроз десни чвор било ког подграфа има степен највише два . Његов 2-језгарни подграф преостане након узастопних брисања чворова степена мање од два, баш оно што је у сенци

У теорији графова, k-дегенерисан граф је неусмерен граф у којем сваки подграф има чворове максималног степена k: то јест, из неког чвора у подграфу излази k или мање грана подграфа. Дегенерација графа је најмања вредност k за које је k-дегенерисан. Дегенерација графа је мера колико је граф редак, и у сталном фактору других мера реткоће као што је Арборицитет графа.

Дегенерација је такође позната као k-језгро броја, ширина, и повезивање, и у суштини је исто као и колоринг намбр (coloring number) или Шекерес-Вилфов број (назван по Шекерес and Вилф (1968)). k-дегенерисани графови се такође називају и k-индуковани графови. Дегенерација графа може се израчунати у линеарном времену алгоритмом који непрестано уклања чвор минималног степена. Повезане компоненте које су остале након што су сви чворови степена мањег од k уклоњени се зову k-језгра графа и дегенерација графа је највећа вредност k такав да има k-језгро.

Примери

Свака шума има или изолован чвор (без грана) или чвор-лист (тачно једна грана); Стога, дрвеће и шуме су 1-дегенерисани графови.

Сваки коначан планаран граф има чвор степена пет или мање; Стога, сваки планаран граф је 5-дегенерисан, и дегенерација било ког планарног графа је највише пет. Слично, сваки аутерпланар (outerplanar) граф има дегенерацију највише два, и аполонијеве мреже имају дегенерацију три.

Барабаши-Алберт модел за генерисање случајних скел-фри (scale free) мрежа има параметар m такав да сваки чвор који се додаје графу има m претходно додатих чворова. Из тога следи да сваки подграф мреже формиране на овај начин има чворове максималног степена m (последњи чвор у подграфу који је додат графу) и Барабаши-Алберт мреже су аутоматски m-дегенерисане.

Сваки k-регуларни граф је дегенерације тачно k. Тачније, дегенерација графа једнака је максималном степену чвора ако и само ако је најмање једна од повезаних компоненти графа регуларно максималног степена. За све остале графове, дегенерација је строго мања од максималног степена.

Дефиниције и еквиваленције

Колоринг намбр (Coloring number) графа G је дефинисан од стране Ердос & Хајнал 1966 тако да је најмање κ за које постоје уређење чворова у G у којој сваки чвор има мање од κ суседа који су раније уређени. Треба разликовати хроматски број од G, минимални број боја потребан за бојење чворова, тако да не постоје два суседна чвора исте боје; редослед који одређује број боја даје наредбу да се обоји чвор у G са колоринг намбр (coloring number), али генерално хроматски број може бити мањи.

Дегенерација графа G је дефинисана од стране Лик & Вајт 1970 као најмање k тако да сваки индуковани подграф од G садржи чвор са k или мање суседа. Дефиниција би била иста ако би се произвољни подграф заменио са индукованим подграфом, с тим да неиндуковани подграф може имати само степене који су мањи или једнаки од степена чвора у подграфу индукованим истим чворовима.

Концепти колоринг намбр (coloring number) и дегенерације су еквивалентни: у сваком коначном графу дегенерација се само мало разликује од колоринг намбр (coloring number). Јер, ако је граф уређен према колоринг намбр (coloring number) k онда у сваком подграфу H чвор који припада H и последњи у редоследу има највише κ − 1 суседа у H. У другом смеру, ако је G k-дегенерисан, онда се редослед са колоринг намбр (coloring number) к + 1 може добити у више наврата проналажењем чвора V са највише k суседа, уклањањем V из графа, уређивањем преосталх чворова, и додавањем V на крају реда.

Трећа, еквивалентна формулација је да је G k-дегенерисан (или има бојење број највише k + 1) ако и само ако се гране од G могу усмерити да формирају директан ациклични граф са излазним степеном k. Такво усмеравање може да се формира усмеравајући сваку грану према ранијем од своје две крајње тачке у бојење број уређењу. У другом смеру, ако је дата оријентација са излазним степеном k, сортирање са колоринг намбр (coloring number) k + 1 може се добити као Тополошко сортирање добијеног усмереног ацикличног графа.

k-језгра

k-језгро графа G је максимални повезан подграф од G у ком су сви чворови најмање степена k. Еквивалентно, то је једна компонента повезаности подграфа од G формирана константним брисањем свих чворова степена мањег од k. Ако непразно k-језгро постоји, онда G има дегенерацију најмање k, и дегенерација од G је највеће k за које G има k-језгро.

Чвор $u$ има језгарност $c$ ако припада $c$-језгру, али не било ком $(c+1)$-језгру.

Концепт k-језгра је уведен за проучавање груписања структура друштвених мрежа и да описују еволуцију случајних графова; такође се примењује у биоинформатици и мрежама за визуелизацију.

Алгоритми

Као што су Матула & Бек 1983 описали, могуће је наћи уређење чворова коначног графа G који оптимизује број боја уређивања, у линеарном времену, константним уклањањем чвора најмањег степена.

Прецизније, следи алгоритам:

• Иницијализује се излазна листа L.
• Рачунање броја d_V за сваки чвор V у G, број суседа V који нису већ у L. У почетку, ови бројеви су само степени чворова.
• Иницијализује се низ D тако да D[i] садржи листу чворова V који нису већ у L за које је d_v = i.
• Иницијализује се k на 0.
• Поновити n пута:
  • Скенирати низ ћелија D[0], D[1], ... док се не пронађе i за које је D[i] непразно.
  • Поставити k на max(k,i).
  • Изабрати чвор V из D[i]. Додати V на почетку L и уклонити га из D[i].
  • За сваки сусед W од V који није већ у L, одузети један од d_W и померити W на ћелију D која одговара новој вредности d_W.

На крају алгоритма, k садржи дегенерацију од G, а L садржи листу чворова у оптималном редоследу за број бојења. i-језгро од G су префикси L која се састоје од чворова додатих на L након што k прво узима вредност већу или једнако од i.

Иницијализовање променљивих L, d_V, D и k може лако да се уради у линеарном времену. Проналажење сваког успешно уклоњеног чвора V и прилагођавање ћелије 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-језгра, али се заснивају на повезаности чворова су објашњени у теорији друштвених мрежа под именом структурне кохезије.

Ако граф има ширину дрвета или ширину стазе највише k, онда је то подграф тетивног графа који има савршени елиминаторни редослед према коме сваки чвор има k претходних суседа. Стога, дегенерација је највише једнака ширини дрвета и ширини стазе. Међутим, постоје графови са ограниченим дегенерацијама и неограниченим ширинама дрвета, као што су мрежни графови.

Као још недоказана Ердос-Бур претпоставка, дегенерације графа G може се довести у везу са Ремзијев број од G, највеће n, тако да сваке две гране бојење n-чворног комплетног графа мора да садржи монохроматску копију од G. Специфично, претпоставка је да за сваку фиксну вредност k, Ремзијев број k-дегенерисаног графа расте линеарно у броју чворова графа.

Бесконачни графови

Иако се концепти дегенерације и бојење број често сматрају у контексту коначних графова, оригинална мотивација за Ердос & Хајнал 1966 била је теорија бесконачних графова. За бесконачни граф G, може се дефинисати број бојења аналогно дефиницији за коначне графове, као најмањи Кардинални број α такав да постоји добро редослед чворова у G у којој сваки чвор има мање од α суседа које су раније у редоследу. Неједнакост између бојења и хроматских бројева важи такође и у овом бесконачном окружењу; Ердос & Хајнал 1966 наводе да је, у време објављивања свог рада, то већ било познато.

Литература

• Altaf-Ul-Amin, M.; Nishikata, K.; Koma, T.; Miyasato, T.; Shinbo, Y.; Arifuzzaman, M.; Wada, C.; Maeda, M.; Oshima, T. (2003), „Prediction of protein functions based on k-cores of protein-protein interaction networks and amino acid sequences” (PDF), Genome Informatics, 14: 498—499, Архивирано из оригинала (PDF) 27. 9. 2007. г., Приступљено 26. 05. 2016 .
• Alvarez-Hamelin, José Ignacio; Dall'Asta, Luca; Barrat, Alain; Vespignani, Alessandro (2005), k-core decomposition: a tool for the visualization of large scale networks, arXiv:cs/0504107  .
• Asahiro, Yuichi; Miyano, Eiji; Ono, Hirotaka; Zenmyo, Kouhei (2006), „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., стр. 11—20, ISBN 978-1-920682-33-0 .
• Bader, Gary D.; Hogue, Christopher W. V. (2003), „An automated method for finding molecular complexes in large protein interaction networks”, BMC Bioinformatics, 4 (1): 2, PMC 149346 , PMID 12525261, doi:10.1186/1471-2105-4-2 .
• Barabási, Albert-László; Albert, Réka (1999), „Emergence of scaling in random networks” (PDF), Science, 286 (5439): 509—512, PMID 10521342, doi:10.1126/science.286.5439.509, Архивирано из оригинала (PDF) 17. 04. 2012. г., Приступљено 26. 05. 2016 .
• Bollobás, Béla (1984), „The evolution of sparse graphs”, Graph Theory and Combinatorics, Proc. Cambridge Combinatorial Conf. in honor of Paul Erdős, Academic Press, стр. 35—57 .
• Burr, Stefan A.; Erdős, Paul (1975), „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 (PDF), Colloq. Math. Soc. János Bolyai, 10, Amsterdam: North-Holland, стр. 214—240, MR 0371701 .
• Chrobak, Marek; Eppstein, David (1991), „Planar orientations with low out-degree and compaction of adjacency matrices” (PDF), Theoretical Computer Science, 86 (2): 243—266, doi:10.1016/0304-3975(91)90020-3 .
• Dean, Alice M.; Hutchinson, Joan P.; Scheinerman, Edward R. (1991), „On the thickness and arboricity of a graph”, Journal of Combinatorial Theory, Series B, 52 (1): 147—151, MR 1109429, doi:10.1016/0095-8956(91)90100-X .
• Dorogovtsev, S. N.; Goltsev, A. V.; Mendes, J. F. F. (2006), „k-core organization of complex networks”, Physical Review Letters, 96 (4): 040601, PMID 16486798, arXiv:cond-mat/0509102 , doi:10.1103/PhysRevLett.96.040601 .
• Erdős, Paul; Hajnal, András (1966), „On chromatic number of graphs and set-systems” (PDF), Acta Mathematica Hungarica, 17 (1–2): 61—99, MR 0193025, doi:10.1007/BF02020444 .
• Freuder, Eugene C. (1982), „A sufficient condition for backtrack-free search”, Journal of the ACM, 29 (1): 24—32, doi:10.1145/322290.322292 .
• Gabow, H. N.; Westermann, H. H. (1992), „Forests, frames, and games: algorithms for matroid sums and applications”, Algorithmica, 7 (1): 465—497, doi:10.1007/BF01758774 .
• Gaertler, Marco; Patrignani, Maurizio (2004), „Dynamic analysis of the autonomous system graph”, Proc. 2nd International Workshop on Inter-Domain Performance and Simulation (IPS 2004) (PDF), стр. 13—24, Архивирано из оригинала (PDF) 22. 07. 2011. г., Приступљено 26. 05. 2016 .
• Irani, Sandy (1994), „Coloring inductive graphs on-line”, Algorithmica, 11 (1): 53—72, doi:10.1007/BF01294263 .
• Jensen, Tommy R.; Toft, Bjarne (2011), Graph Coloring Problems, Wiley Series in Discrete Mathematics and Optimization, 39, John Wiley & Sons, ISBN 9781118030745 .
• Kirousis, L. M.; Thilikos, D. M. (1996), „The linkage of a graph” (PDF), SIAM Journal on Computing, 25 (3): 626—647, doi:10.1137/S0097539793255709, Архивирано из оригинала (PDF) 21. 7. 2011. г., Приступљено 26. 05. 2016 .
• Kowalik, Łukasz (2006), „Approximation scheme for lowest outdegree orientation and graph density measures”, Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006), Springer-Verlag, 4288: 557—566, doi:10.1007/11940128_56 .
• Lick, Don R.; White, Arthur T. (1970), „k-degenerate graphs”, Canadian Journal of Mathematics, 22: 1082—1096, doi:10.4153/CJM-1970-125-1, Архивирано из оригинала 23. 07. 2012. г., Приступљено 26. 05. 2016 .
• Łuczak, Tomasz (1991), „Size and connectivity of the k-core of a random graph”, Discrete Mathematics, 91 (1): 61—68, doi:10.1016/0012-365X(91)90162-U, Архивирано из оригинала 09. 03. 2016. г., Приступљено 26. 05. 2016 .
• Matula, D. W. (1968), „A min-max theorem for graphs with application to graph coloring”, SIAM 1968 National Meeting, SIAM Review, 10 (4): 481—482, doi:10.1137/1010115 .
• Matula, D. W.; Beck, L. L. (1983), „Smallest-last ordering and clustering and graph coloring algorithms”, Journal of the ACM, 30 (3): 417—427, MR 0709826, doi:10.1145/2402.322385 .
• Moody, James; White, Douglas R. (2003), „Structural cohesion and embeddedness: a hierarchical conception of social groups”, American Sociological Review, 68 (1): 1—25, doi:10.2307/3088904 .
• Robertson, Neil; Seymour, Paul (1984), „Graph minors. III. Planar tree-width”, Journal of Combinatorial Theory, Series B, 36 (1): 49—64, doi:10.1016/0095-8956(84)90013-3 .
• Seidman, Stephen B. (1983), „Network structure and minimum degree”, Social Networks, 5 (3): 269—287, doi:10.1016/0378-8733(83)90028-X .
• Szekeres, George; Wilf, Herbert S. (1968), „An inequality for the chromatic number of a graph”, Journal of Combinatorial Theory, 4: 1—3, doi:10.1016/S0021-9800(68)80081-X .
• Venkateswaran, V. (2004), „Minimizing maximum indegree”, Discrete Applied Mathematics, 143 (1–3): 374—378, doi:10.1016/j.dam.2003.07.007 .
• Wuchty, S.; Almaas, E. (2005), „Peeling the yeast protein network”, Proteomics, 5 (2): 444—449, PMID 15627958, doi:10.1002/pmic.200400962 .