Арборицитет

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

Арборицитет неусмереног графа је минималан број Шума у којима се налазе гране графа . Еквивалентно је минималаном броју разапињућих шума потребних да се обухвате све гране графа.

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

Подела комплетног бипартитног графаK4,4 у три шуме, што показује да је арборицитет графа три.

Слика приказује комплетни бипартитни граф K4,4, са бојама које показују поделу грана у три шуме. K4,4 не могу бити подељене у мање шуме, јер свака шума , на осам чворова , има највише седам грана, док је граф има укупно шеснаест грана, дупло већи број грана у једној шуми. Дакле, арборицитет K4,4 је три.

Арборицитет као мера густине[уреди]

Арборицитет графа је мера која даје информцију о густини графа: графови са више грана имају висок арборицитет, и графови са високим арборицитетом морају имати густ подграф.

Детаљније , као и свака n-степена шума има највише n-1 грану, арборицитет графа са n чворова и m грана је најмање \lceil m/(n-1)\rceil . Поред тога, подграф било ког графа не може имати арборицитет већи од самог графа, илити ; арборицитет графа мора бити најмање максимални арборицитет било ког његовог подграфа. Nash-Williams је доказао да ове две чињенице могу да се комбинују чиме окарактеришу арборицитет: ако узмемо да nS и mS означавају број чворова и грана, респективно, једног подграфа S , задатог графа, онда арборицитет графа износи \max\{\lceil m_S/(n_S-1)\rceil\}.

Сваки планарни граф са n чворова има највише 3n-6, из чега следи по формули Nash-Williams-a, да планарни графови имају арборицитет највише три . Schnyder је користио посебно разлагање планарног графа у три шуме : Schnyder-ово дрво да пронађе праволинијско уграђивање једног планарног графа у мрежу у малом простору.

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

Арборицитет графа се може изразити као посебан случај општије матроидне поделе проблема, у коме се изражава скуп елемената матроид као заједница малог броја независних скупова. Као последица тога, арборицити може се израчунати полинома-алгоритам [1].

Сродни концепти[уреди]

Арборицитет-звезда графа је величина минималне шуме, код које је свако стабло Звезда (стабло са највише једним чвором без листове), у који гране графа могу бити подељене. Ако дрво није звезда, њен арборицитет-звезда је два, што се може видети поделом грана у две подгрупе : парних и непарних растојањима од корена стабла, респективно. Дакле, арборицитет-звезда једног графа је барем једнак арборицитет-у, а максимално једнак двоструком арборицитет-у.

Линеарни арборицитет графа је величина минималне линеарне шуме (шума у којој су сви чворови инцидентни са највише две гране) у којој могу да се налазе гране графа. Линеарни арборицитет графа је уско повезан са максималним степеном графа и његовим нагибним бројем.

Псеудоарборицитет графа је минималан број псеудошума-а у којима су његове гране постављене. Еквивалентно, то је максимални однос грана и чворова из било ког подграфа . Као и код арборицитета, псеудоарборицитет има матроидну структуру што омогућава да се ефикасно израчунава [1].

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

Дегенерација графа је максимум, свих индукованих подграфа графа, са најмањим степеном чворова у подграфу. Дегенерација графа са арборицитетом a је најмање једнака a а највише једнака 2a-1. Број бојења графа, такође познат као Szekeres-Wilf-ов број [2] .

Снага графа је фракциона вредност чији цео део даје максималан број дисјунктних разапињућих стабала, која се могу уцртати на графу. То је проблем паковања који је дуалан проблему покривања вођен арборицитетом. Ова два параметра су заједно изучавали Tutte, W. T. i Nash-Williams.

Напомене[уреди]

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

  1. ^ а б Gabow & Westermann 1992
  2. ^ Szekeres & Wilf 1968, је увек једнак дегенерацији плус 1 Jensen & Toft 1995, стр. 77f.