Back

ⓘ Компоненте повезаности (теорија графова)




Компоненте повезаности (теорија графова)
                                     

ⓘ Компоненте повезаности (теорија графова)

У теорији графова, повезана компонента неусмереног графа је подграф у ком су било која два чвора међусобно повезана путевима, и који није повезан са додатним чворовима у суперграфу. На пример, у графу приказаном на илустрацији са десне стране се налазе три повезане компоненте. Граф које је повезан сам са собом, има тачно једну повезану компоненту, чинећи цео граф.

                                     

1. Релација еквиваленције

Алтернативни начин да се дефинише повезана компонента укључује класе еквиваленције од релације еквиваленције која је дефинисана на чворовима графа. У неусмереном графу, чвор v је достижан од чвора u ако постоји пут од u до v. У овој дефиницији, један чвор се рачуна као пут дужине нула, а исти чвор може да се појави више од једног пута у обиласку. Достизање је релација еквиваленције, пошто:

  • Је симетрична: Ако постоји пут од u до v, сама грана формира пут од v до u.
  • Је рефлексивна: Постоји тривијални пут од дужине нула од било ког чвора до самог себе.
  • Је транзитивна: Ако постоји пут од u до v и пут од v до w, ова два пута могу бити спојена заједно тако да формирају пут од u до w.

Повезане компоненте су онда индуковани подграфи које формирају класе еквиваленције у овој релацији.

                                     

2. Број компоненти повезаности

Број компоненти повезаности је важна тополошка инваријанта графа. У тополошкој теорији графова, број компоненти повезаности може да се интерпретира као нулти Бетијев број графа. У алгебарској теорији графова број компоненти повезаности је једнак вишеструкости 0 као сопствени вектор од графа Лапласове матрице. Такође је и индекс првог коефицијента различитог од нуле од хроматског полинома графа. Број компоненти повезаности играју кључну улогу у Тутовој теореми карактеришући графове који имају савршено поклапање, и у дефиницији тежине графова.

                                     

3. Алгоритми

Једноставно је да се израчунају компоненте повезаности графа у линеарном времену у погледу броја чворова и путева графа коришћењем било претраге у ширину или претраге у дубину. У било ком случају, претрага која почиње у неком одређеном чвору v пронаћи ће целокупну повезану компоненту која садржи v и не више пре повратка. Да бисмо пронашли све повезане компоненте графа, идемо петљом кроз чворове, започињући нову претрагу у ширину или дубину кад год петља достигне чвор који већ није укључен у претходно пронађеној компоненти повезаности. Хопкрофт и Тарџан 1973) описују овај алгоритам у суштини, и наводе да је у том тренутку било "добро познато".

Постоје и ефикасни алгоритми за динамичко праћење повезаних компоненти графа док се чворови и гране додају, као једноставна примена система дисјунктних структура података. Ови алгоритми захтевају амортизовано Oαn) време операције, код којих додајући чворове и путеве, и одређивање повезане компоненте, где су обе операција, и αn је врло споро растућа инверзна, од врло брзо растуће Акерманове функције. Сличан проблем представља праћење повезаних компоненти док се све гране бришу из графа, једна по једна; постоји алгоритам за решавање овог константног времена по упиту, и O|V||E| време да се одржи структура података; ово је амортизована цена од O|V| по брисању пута. За дрвета, цена може да се смањи до Oq + |V| log |V|, или Olog |V| амортизована цена по обрисаном путу.

Истраживачи су такође проучавали алгоритме за проналажење повезујућих компоненти у више ограниченим моделима рачунања, као што су програми у којима је радна меморија ограничена на логаритамски број битова дефинисана комплексном класом L. Левис и Пападимитроу 1982 су се питали да ли је могуће да се тестира у логаритамском простору да ли два чвора припадају истој компоненти повезаности неког неусмереног графа, и дефинисали су комплексност SL класе проблема где је логаритамски простор једнак повезаности. Коначно је Реинголд 2008 успео да пронађе алгоритам за решавање овог проблема повезивања у логаритамског простору, показујући да је L = SL.



                                     
  • на компоненте, тако да су компоненте исте величине и да постоји повезаност између компоненти Подела партиционисање графова има важну улогу у научном
  • области теорије графова и теорије матроида. Татово истраживање у области графова показало се од изузетног значаја. У време када је теорија графова још увек
  • računarstvu i teoriji grafova struktura dinamičkog povezivanja je struktura podataka koja dinamički održava informacije o komponentama povezanosti grafa. Skup
  • U informatici i teoriji grafova Kargerov algoritam je algoritam nasumične metode koji odreduje minimalan rez povezanog grafa. Izmislio ga je Dejvid Karger

Users also searched:

...