Разапињуће стабло

С Википедије, слободне енциклопедије
Разапињуће дрво (плаве теске гране) решетке графа

У математичком пољу теорије графова разапињуће стабло Т повезаног, неусмереног графа је стабло које се састоји од свих врхова и неких (или можда чак и свих) грана од Г. Неформално, разапињуће стабло од Г представља одабир грана од Г које формирају дрво које обухвата сваки врх. То значи, сваки врх постоји у дрвету, али без циклова (или петљи). С друге стране, сваки мост од Г мора припадати Т.

Разапињуће стабло повезаног графа Г се такође може дефинисати као максималан сет грана од Г које не садрже циклове, или као минималан сет грана које садрже све врхове.

У одређеним пољима теорије графова често је корисно пронаћи минимално разапињуће стабло оптерећеног графа. Други проблеми оптимизације разапињућег дрвећа су такође проучавани, укључујући и максимално разапињуће дрво, минимално дрво које обухвата најмање к врхова, минимално разапињуће дрво са највише к грана по врху степеном ограничено разапињуће дрво, разапињуће дрво са највећим бројем листова (уско повезано са најмањим доминирајућим скупом), разапињуће дрво са најмање листова (уско повезано са Проблемом Хамилтовог пута), разапињуће дрво минималног пречника, и разапињуће дрво минималне дилатације.

Основни циклуси[уреди | уреди извор]

Додајући само једну грану у разапињуће стабло ће створити цикл; такав цикл се назива основни цикл. Постоји посебан фундаментални цикл за сваку ивицу; тако, постоји 1-1 кореспонденција између основних циклова и грана које нису у разапињућем стаблу. За повезан граф са V врхова, било које разапињуће дрво ће имати V-1 грана, и тако, граф од Е грана ће имати Е-V+1 основних циклова. За било које дато разапињуће стабло ови циклови ће формирати базу за простор циклова.

Сличан појму основног цикла је појам основни подскуп. Брисањем само једне гране разапињућег стабла, врхови ће бити партиционисани у два дисјунктна подскупа. Основни подскуп је дефинисан као скуп грана које морају бити уклоњене из графа Г да би се остварила иста партиција. Тако, постоји тачно V-1 основних подскупова графа, по један за сваку грану разапињућег стабла.

Дуалност између основних подскупова и основних циклова је уведена уз напомену да се гране цикла које нису у разапињућем стаблу могу појавити само у подскуповима на другим гранама цикла; и обрнуто: гране подскупа се могу појавити само у оним цикловима који садрже одговарајућу грану подскупа.

Разапињуће шуме[уреди | уреди извор]

Разапињућа шума је тип подграфа који генерализује концепт разапињућег дрвета. Како год, постоје две дефиниције у заједничкој употреби. Једна је да је разапињућа шума подграф који садржи разапињуће дрво у свакој повезаној компоненти графа. (Еквивалентно, то је максималан слободан цикл подграфа.) Ова дефиниција је заједничка у компјутерској науци и оптимизацији. То је такође дефиниција која се користи када се дискутују минималне разапињуће шуме, генерализација која се односи на неповезане графове који обухватају минимум разапињућег дрвећа. Друга дефиниција, заједничка у теорији графова, је да је разапињућа шума било који подграф који је обоје - шума (не садржи циклове) и разапињући (садржи сваки чвор).

Бројање разапињућих стабала[уреди | уреди извор]

Кајлејева формула броји број разапињућих стабала у комплетном графу. Постоји: стабала у ,
стабала у , и
стабала у .

Број т(Г) разапињућих стабала повезаног графа је добро проучена инваријанта. У неким случајевима, лако је израчунати т(Г) директно. На пример, ако је Г дрво само по себи, т(Г)=1, а ако је Г цикличан граф са н врхова, онда је т(Г) = н. За било који граф Г, број т(Г) се може израчунати користећи Киркхову матрица-дрво теорему.

Кајлејева формула је формула за број разапињућих стабала у комплетном графу са н врхова. Формула каже да . Други начин исказивања Кајлејеве формуле је да постоји тачно обележених стабала са н врхова. Кајлејева формула може бити доказана користећи Киркхову матрица-дрво теорему или преко Пруферовог кода.

Ако је Г потпун двострани граф тада је , док је Г н-димензиони хиперкоцкасти граф , тада је . Ове формуле су такође последице матрица-дрво теореме.

Ако је Г мултиграф и е је ивица од Г, онда број т(Г) разапињућих стабала задовољава брисање-контракција рекуренцију т(Г)=т(Г-е)+т(Г/е), где је Г-е мултиграф добијен брисањем е и Г/е је контракција од Г по е, где мноштво грана које се јављају из ове контракције нису избрисане.

Хомогена разапињућа стабла[уреди | уреди извор]

Разапињуће стабло изабрано насумично од свих разапињуцих стабала са једнаком вероватноћом се назива хомогено разапињуће дрво (УСТ/ХРС). Овај модел је обимно истраживан у вероватноћи и математичкој физици.

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

Класични алгоритам разапињућег стабла, претрага у дубину (ДФС - дептх-фирст сеарцх), је настао захваљујући Роберту Тарџану. Други, важан алгоритам је базиран на претрази у ширину (БФС - бреадтх-фирст сеарцх).

Паралелни алгоритми типично заузимају другачији приступ од ДФС и БФС. Халперин и Зwицк су дизајнирали оптимално насумични паралелан алгоритам који ради у логаритамском времену, О(лог н), са великом вероватноћом за ЕРЕW ПРАМ. Схилоацх-Висхкин алгоритам, настао захваљујући Yосси Схилоацх и Узи Висхкин је основни за многе паралелне имплементације. За Бадер и Конгов алгоритам је показано да ради најбрже у пракси на разноврсним графовима.

Најчешће дистрибуиран алгоритам је Разапињуће Дрво Протокол, коришћен од стране "ОСИ линк лаyер"-Слој везе уређаја како би створили разапињуће дрво које користи већ постојеће везе као изворне графове у жељи да избегну олује при емитовању.

Такође погледај[уреди | уреди извор]

Минимално разапињуће стабло