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,[1] širina,[2] i povezivanje,[3] i u suštini je isto kao i koloring nambr (coloring number)[4] ili Šekeres-Vilfov broj (nazvan po Šekeres and Vilf (1968)). k-degenerisani grafovi se takođe nazivaju i k-indukovani grafovi.[5] Degeneracija grafa može se izračunati u linearnom vremenu algoritmom koji neprestano uklanja čvor minimalnog stepena.[6] 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

uredi

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,[7] i apolonijeve mreže imaju degeneraciju tri.

Barabaši-Albert model za generisanje slučajnih skel-fri (scale free) mreža[8] 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.[9]

Definicije i ekvivalencije

uredi

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).[10] 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.[11] 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

uredi

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   ima jezgarnost   ako pripada  -jezgru, ali ne bilo kom  -jezgru.

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

Algoritmi

uredi

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 dV 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 dv = 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 dW i pomeriti W na ćeliju D koja odgovara novoj vrednosti dW.

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, dV, 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 dV 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

uredi

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.[16] Debljina je u okviru stalnog faktora aboriciteta, a samim tim i degeneracije.[17]

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.[18]

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.[19]

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.[20]

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.[21]

Beskonačni grafovi

uredi

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.

Reference

uredi
  1. ^ a b Barder & Hog 2003
  2. ^ Frojder 1982
  3. ^ Kirouzis & Tilikos 1996
  4. ^ Erdos & Hajnal 1966
  5. ^ Irani 1994
  6. ^ Matula & Bek 1983
  7. ^ Lik & Vajt 1970
  8. ^ Barabaši & Albert 1999
  9. ^ Džensen & Toft 2011
  10. ^ Matula 1968; Lik & Vajt 1970
  11. ^ Hrobak & Epštajn 1991
  12. ^ Sajdman 1983
  13. ^ Bolobas 1984; Lucak 1991;Dorogovstev, Goltsev & Mendes 2006
  14. ^ Altaf-Ul-Amin et al. 2003; Vučti & Almas 2005
  15. ^ Gertler & Patrignani 2004; Alvarez-Hamelin et al. 2005
  16. ^ Hrobak & Njištajn 1991; Gabov & Vesterman 1992; Venkatesvaran 2004; Ašakiro et al. 2006; Kovalik 2006
  17. ^ Dean, Hučinson & Šajnerman (1991).
  18. ^ Erdos & Hajnal 1966; Šekeres & Vilf 1968
  19. ^ Mudi & Vajt 2003
  20. ^ Robertson & Sejmour 1984
  21. ^ Bar & Erdos 1975

Literatura

uredi