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

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

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

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

Примери[уреди]

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

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

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

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

Дефиниције и еквиваленције[уреди]

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

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

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

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

k-језгра[уреди]

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

Чвор има језгарност ако припада -језгру, али не било ком -језгру.

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

Алгоритми[уреди]

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

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

  • Иницијализује се излазна листа L.
  • Рачунање броја dV за сваки чвор V у G, број суседа V који нису већ у L. У почетку, ови бројеви су само степени чворова.
  • Иницијализује се низ D тако да D[i] садржи листу чворова V који нису већ у L за које је dv = 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, одузети један од dW и померити W на ћелију D која одговара новој вредности dW.

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

Иницијализовање променљивих L, dV, D и k може лако да се уради у линеарном времену. Проналажење сваког успешно уклоњеног чвора V и прилагођавање ћелије D да садржи суседе V узима пропорционално времена у преузимању, сразмерно вредности dV на том кораку; али збир тих вредности је број грана графа (свака грана доприноси као члану збира за касније своја два крајње тачке) тако да је укупно време линеарно.

Однос других параметара у графу[уреди]

Ако је граф G оријентисан ацикличан са излазним степенном k, онда његове гране могу бити подељене у k шума, избором једне шуме за сваку излазну грану сваког чвора. Дакле, Арборицитет за G је једнак његовој дегенерацији. У другом правцу, граф са n чворова који се може поделити на k шума има највише k(n − 1) грана и стога има чвор степена највише 2k− 1 – дакле, дегенерација је два пута мања од арборицитета . Такође се може израчунати у полиномијалном времену оријентација графа који минимизира излазни степен али није потребно да буде ацикличан. Гране графа са таквом оријентацијом могу бити подељене на исти начин у k псеудошума и обратно свака подела грана графа у k псеудошума доводи до излазним степеном-k оријентације (одабиром излазног степена-1 оријентације за сваку псеудошуму), тако да је минимални излазни степен такве оријентације псеудоаборицитет, што је опет једнако дегенерацији. [16] Дебљина је у оквиру сталног фактора аборицитета, а самим тим и дегенерације.[17]

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

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

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

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

Бесконачни графови[уреди]

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

Референце[уреди]

Литература[уреди]