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

Degeneracy

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

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

Примери

Свака шума има или изолован чвор (без грана) или чвор-лист (тачно једна грана); Стога, дрвеће и шуме су 1-дегенерисани графови. Сваки коначан планаран граф има чвор степена пет или мање; Стога, сваки планаран граф је 5-дегенерик, и дегенерација било ког планарног графа је највише пет. Слично, сваки оутерпланар граф има дегенерацију највише два, и аполонијеве мреже имају дегенерацију три. Барабаши-Алберт модел за генерисање случајних сцале-фрее мрежа има параметар m такав да сваки чвор који се додаје графу има m претходно додатих чворова. Из тога следи да сваки подграф мреже формиране на овај начин има чворове максималног степена m (последњи чвор у подграфу који је додат графу) и Барабаши-Алберт мреже су аутоматски м-дегенерик.

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

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

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

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

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

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

k-језгра

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

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

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

Algoritmi

Као сто су Матула & Бек (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 оријентисан ацикличан са излазним степенном к, онда његове гране могу бити подељене у к шума, избором једне шуме за сваку излазну грану сваког чвора. Дакле, Арборицитет за G је једнак његовој дегенерацији. У другом правцу, граф са n чворова који се може поделити на к шума има највише к(n − 1) грана и стога има чвор степена највише 2k− 1 – дакле, дегенерација је два пута мања од арборицитета . Такође се може израчунати у полиномијалном времену оријентација графа који минимизира оутдегрее али није потребно да буде ацикличан. Гране графа са таквом оријентацијом могу бити подељене на исти начин у k псеудошума и обратно свака подела грана графа у k псеудошума доводи до оутдегрее-k оријентације (одабиром оутдегрее-1 оријентације за сваку псеудошуму), тако да је минимални оутдегрее такве оријентације псеудоаборицитет, што је опет једнако дегенерацији. Дебљина је у оквиру сталног фактора аборицитета, а самим тим и дегенерације.

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

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

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

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

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

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

Reference

• 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 .
• 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 1-920682-33-3 .
• 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 .
• 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 .
• 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 .
• 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 .
• Ł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 .
• 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 .

Категорије:Алгоритми о графовима