Degenerisani grafovi

U teoriji grafova, k-degenerisan graf je neusmeren graf u kojem svaki podgraf ima čvorove maksimalnog stepena k: to jest, iz nekog čvora u podgrafu izlazi k ili manje grana podgrafa. Degeneracija grafa je najmanja vrednost k za koje je k-degenerisan. Degeneracija grafa je mera koliko je graf redak, i u stalnom faktoru drugih mera retkoće kao što je Arboricitet grafa.

2-degenerisan graf:svaki čvor ima najviše dva suseda sa svoje leve strane, tako da skroz desni čvor bilo kog podgrafa ima stepen najviše dva . Njegov 2-jezgarni podgraf preostane nakon uzastopnih brisanja čvorova stepena manje od dva, baš ono što je u senci

Degeneracija je takođe poznata kao k-jezgro broja, širina, i povezivanje, i u suštini je isto kao i koloring nambr (coloring number) ili Šekeres-Vilfov broj (nazvan po Šekeres and Vilf (1968)). k-degenerisani grafovi se takođe nazivaju i k-indukovani grafovi. Degeneracija grafa može se izračunati u linearnom vremenu algoritmom koji neprestano uklanja čvor minimalnog stepena. Povezane komponente koje su ostale nakon što su svi čvorovi stepena manjeg od k uklonjeni se zovu k-jezgra grafa i degeneracija grafa je najveća vrednost k takav da ima k-jezgro.

Primeri

Svaka šuma ima ili izolovan čvor (bez grana) ili čvor-list (tačno jedna grana); Stoga, drveće i šume su 1-degenerisani grafovi.

Svaki konačan planaran graf ima čvor stepena pet ili manje; Stoga, svaki planaran graf je 5-degenerisan, i degeneracija bilo kog planarnog grafa je najviše pet. Slično, svaki auterplanar (outerplanar) graf ima degeneraciju najviše dva, i apolonijeve mreže imaju degeneraciju tri.

Barabaši-Albert model za generisanje slučajnih skel-fri (scale free) mreža ima parametar m takav da svaki čvor koji se dodaje grafu ima m prethodno dodatih čvorova. Iz toga sledi da svaki podgraf mreže formirane na ovaj način ima čvorove maksimalnog stepena m (poslednji čvor u podgrafu koji je dodat grafu) i Barabaši-Albert mreže su automatski m-degenerisane.

Svaki k-regularni graf je degeneracije tačno k. Tačnije, degeneracija grafa jednaka je maksimalnom stepenu čvora ako i samo ako je najmanje jedna od povezanih komponenti grafa regularno maksimalnog stepena. Za sve ostale grafove, degeneracija je strogo manja od maksimalnog stepena.

Definicije i ekvivalencije

Koloring nambr (Coloring number) grafa G je definisan od strane Erdos & Hajnal 1966 tako da je najmanje κ za koje postoje uređenje čvorova u G u kojoj svaki čvor ima manje od κ suseda koji su ranije uređeni. Treba razlikovati hromatski broj od G, minimalni broj boja potreban za bojenje čvorova, tako da ne postoje dva susedna čvora iste boje; redosled koji određuje broj boja daje naredbu da se oboji čvor u G sa koloring nambr (coloring number), ali generalno hromatski broj može biti manji.

Degeneracija grafa G je definisana od strane Lik & Vajt 1970 kao najmanje k tako da svaki indukovani podgraf od G sadrži čvor sa k ili manje suseda. Definicija bi bila ista ako bi se proizvoljni podgraf zamenio sa indukovanim podgrafom, s tim da neindukovani podgraf može imati samo stepene koji su manji ili jednaki od stepena čvora u podgrafu indukovanim istim čvorovima.

Koncepti koloring nambr (coloring number) i degeneracije su ekvivalentni: u svakom konačnom grafu degeneracija se samo malo razlikuje od koloring nambr (coloring number). Jer, ako je graf uređen prema koloring nambr (coloring number) k onda u svakom podgrafu H čvor koji pripada H i poslednji u redosledu ima najviše κ − 1 suseda u H. U drugom smeru, ako je G k-degenerisan, onda se redosled sa koloring nambr (coloring number) k + 1 može dobiti u više navrata pronalaženjem čvora V sa najviše k suseda, uklanjanjem V iz grafa, uređivanjem preostalh čvorova, i dodavanjem V na kraju reda.

Treća, ekvivalentna formulacija je da je G k-degenerisan (ili ima bojenje broj najviše k + 1) ako i samo ako se grane od G mogu usmeriti da formiraju direktan aciklični graf sa izlaznim stepenom k. Takvo usmeravanje može da se formira usmeravajući svaku granu prema ranijem od svoje dve krajnje tačke u bojenje broj uređenju. U drugom smeru, ako je data orijentacija sa izlaznim stepenom k, sortiranje sa koloring nambr (coloring number) k + 1 može se dobiti kao Topološko sortiranje dobijenog usmerenog acikličnog grafa.

k-jezgra

k-jezgro grafa G je maksimalni povezan podgraf od G u kom su svi čvorovi najmanje stepena k. Ekvivalentno, to je jedna komponenta povezanosti podgrafa od G formirana konstantnim brisanjem svih čvorova stepena manjeg od k. Ako neprazno k-jezgro postoji, onda G ima degeneraciju najmanje k, i degeneracija od G je najveće k za koje G ima k-jezgro.

Čvor $u$ ima jezgarnost $c$ ako pripada $c$-jezgru, ali ne bilo kom $(c+1)$-jezgru.

Koncept k-jezgra je uveden za proučavanje grupisanja struktura društvenih mreža i da opisuju evoluciju slučajnih grafova; takođe se primenjuje u bioinformatici i mrežama za vizuelizaciju.

Algoritmi

Kao što su Matula & Bek 1983 opisali, moguće je naći uređenje čvorova konačnog grafa G koji optimizuje broj boja uređivanja, u linearnom vremenu, konstantnim uklanjanjem čvora najmanjeg stepena.

Preciznije, sledi algoritam:

• Inicijalizuje se izlazna lista L.
• Računanje broja d_V za svaki čvor V u G, broj suseda V koji nisu već u L. U početku, ovi brojevi su samo stepeni čvorova.
• Inicijalizuje se niz D tako da D[i] sadrži listu čvorova V koji nisu već u L za koje je d_v = i.
• Inicijalizuje se k na 0.
• Ponoviti n puta:
  • Skenirati niz ćelija D[0], D[1], ... dok se ne pronađe i za koje je D[i] neprazno.
  • Postaviti k na max(k,i).
  • Izabrati čvor V iz D[i]. Dodati V na početku L i ukloniti ga iz D[i].
  • Za svaki sused W od V koji nije već u L, oduzeti jedan od d_W i pomeriti W na ćeliju D koja odgovara novoj vrednosti d_W.

Na kraju algoritma, k sadrži degeneraciju od G, a L sadrži listu čvorova u optimalnom redosledu za broj bojenja. i-jezgro od G su prefiksi L koja se sastoje od čvorova dodatih na L nakon što k prvo uzima vrednost veću ili jednako od i.

Inicijalizovanje promenljivih L, d_V, D i k može lako da se uradi u linearnom vremenu. Pronalaženje svakog uspešno uklonjenog čvora V i prilagođavanje ćelije D da sadrži susede V uzima proporcionalno vremena u preuzimanju, srazmerno vrednosti d_V na tom koraku; ali zbir tih vrednosti je broj grana grafa (svaka grana doprinosi kao članu zbira za kasnije svoja dva krajnje tačke) tako da je ukupno vreme linearno.

Odnos drugih parametara u grafu

Ako je graf G orijentisan acikličan sa izlaznim stepennom k, onda njegove grane mogu biti podeljene u k šuma, izborom jedne šume za svaku izlaznu granu svakog čvora. Dakle, Arboricitet za G je jednak njegovoj degeneraciji. U drugom pravcu, graf sa n čvorova koji se može podeliti na k šuma ima najviše k(n − 1) grana i stoga ima čvor stepena najviše 2k− 1 – dakle, degeneracija je dva puta manja od arboriciteta . Takođe se može izračunati u polinomijalnom vremenu orijentacija grafa koji minimizira izlazni stepen ali nije potrebno da bude acikličan. Grane grafa sa takvom orijentacijom mogu biti podeljene na isti način u k pseudošuma i obratno svaka podela grana grafa u k pseudošuma dovodi do izlaznim stepenom-k orijentacije (odabirom izlaznog stepena-1 orijentacije za svaku pseudošumu), tako da je minimalni izlazni stepen takve orijentacije pseudoaboricitet, što je opet jednako degeneraciji. Debljina je u okviru stalnog faktora aboriciteta, a samim tim i degeneracije.

k-degenerisan graf ima hromatski broj najviše k + 1; to je dokazano indukcijom po broju čvorova koji je potpuno isti kao dokaz teoreme šest-boja za planarne grafove. Pošto je hromatski broj gornja granica maksimalne klike, ova druga invarijanta je takođe najveće degeneracije plus jedan. Korišćenjem algoritma pohlepnog bojenja na uređivanje sa optimalnim brojem bojenja, može se obojiti k-degenerisani graf koristeći najviše k + 1 boja.

Graf sa k povezanih čvorova je graf koji ne može biti podeljen u više od jedne komponente uklanjanjem manje od k čvorova, ili ekvivalentno graf u kom se svaki par čvorova može povezati sa k čvorovima-disjunktnim stazama. Budući da ovi putevi moraju da napuste par od dva čvora preko disjunktnih grana, graf sa k povezanih čvorova mora imati degeneraciju najmanje k. Koncepti koji se odnose na k-jezgra, ali se zasnivaju na povezanosti čvorova su objašnjeni u teoriji društvenih mreža pod imenom strukturne kohezije.

Ako graf ima širinu drveta ili širinu staze najviše k, onda je to podgraf tetivnog grafa koji ima savršeni eliminatorni redosled prema kome svaki čvor ima k prethodnih suseda. Stoga, degeneracija je najviše jednaka širini drveta i širini staze. Međutim, postoje grafovi sa ograničenim degeneracijama i neograničenim širinama drveta, kao što su mrežni grafovi.

Kao još nedokazana Erdos-Bur pretpostavka, degeneracije grafa G može se dovesti u vezu sa Remzijev broj od G, najveće n, tako da svake dve grane bojenje n-čvornog kompletnog grafa mora da sadrži monohromatsku kopiju od G. Specifično, pretpostavka je da za svaku fiksnu vrednost k, Remzijev broj k-degenerisanog grafa raste linearno u broju čvorova grafa.

Beskonačni grafovi

Iako se koncepti degeneracije i bojenje broj često smatraju u kontekstu konačnih grafova, originalna motivacija za Erdos & Hajnal 1966 bila je teorija beskonačnih grafova. Za beskonačni graf G, može se definisati broj bojenja analogno definiciji za konačne grafove, kao najmanji Kardinalni broj α takav da postoji dobro redosled čvorova u G u kojoj svaki čvor ima manje od α suseda koje su ranije u redosledu. Nejednakost između bojenja i hromatskih brojeva važi takođe i u ovom beskonačnom okruženju; Erdos & Hajnal 1966 navode da je, u vreme objavljivanja svog rada, to već bilo poznato.

Literatura

• 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, Arhivirano iz originala (PDF) 27. 9. 2007. g., Pristupljeno 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., str. 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, Arhivirano iz originala (PDF) 17. 04. 2012. g., Pristupljeno 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, str. 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, str. 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), str. 13—24, Arhivirano iz originala (PDF) 22. 07. 2011. g., Pristupljeno 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, Arhivirano iz originala (PDF) 21. 7. 2011. g., Pristupljeno 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, Arhivirano iz originala 23. 07. 2012. g., Pristupljeno 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, Arhivirano iz originala 09. 03. 2016. g., Pristupljeno 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 .