Википедија:Песак

Из Википедије, слободне енциклопедије
Песак

Добро дошли у Песак!


Ова страница служи за увежбавање мењања текста. Да бисте почели, кликнитe наово дугме или на „Уреди” (при врху странице), потом начините жељене измене, те кликните на Сачувај страницу (при дну оквира за уређивање). Такође, можете користити и Прикажи претпреглед да бисте видели своје измене без да исте буду сачуване.

Имајте на уму да ниједна од Ваших измена неће заувек остати сачувана на овој страници, јер се њен садржај често мења од стране других корисника и повремено — ботовским изменама — брише.

Уколико желите да уређујете „чист” песак, кликнитеовде.

За експериментисање са шаблонима користите Песак за шаблоне.

gvv


Ed NL icon.png
Овај чланак је део пројекта семинарских радова на Математичком факултету у Београду.
Датум уноса: март—мај 2016.
Википедијанци: Ова група студената ће уређивати у ГИП-у и молимо вас да не пребацујете овај чланак у друге именске просторе Википедије.
Позивамо вас да помогнете студентима при уређивању и допринесете да њихови уноси буду што квалитетнији.

Degeneracy[уреди]

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


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

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

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

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


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

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

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

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


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


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

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

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

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



Algoritmi[уреди]

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


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

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

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


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


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

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



Beleske[уреди]

Reference[уреди]


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