Компоненте повезаности (теорија графова)
У теорији графова, повезана компонента неусмереног графа је подграф у ком су било која два чвора међусобно повезана путевима, и који није повезан са додатним чворовима у суперграфу. На пример, у графу приказаном на илустрацији са десне стране се налазе три повезане компоненте. Граф које је повезан сам са собом, има тачно једну повезану компоненту, чинећи цео граф.
Релација еквиваленције уреди
Алтернативни начин да се дефинише повезана компонента укључује класе еквиваленције од релације еквиваленције која је дефинисана на чворовима графа. У неусмереном графу, чвор v је достижан од чвора u ако постоји пут од u до v. У овој дефиницији, један чвор се рачуна као пут дужине нула, а исти чвор може да се појави више од једног пута у обиласку. Достизање је релација еквиваленције, пошто:
- Је рефлексивна: Постоји тривијални пут од дужине нула од било ког чвора до самог себе.
- Је симетрична: Ако постоји пут од u до v, сама грана формира пут од v до u.
- Је транзитивна: Ако постоји пут од u до v и пут од v до w, ова два пута могу бити спојена заједно тако да формирају пут од u до w.
Повезане компоненте су онда индуковани подграфи које формирају класе еквиваленције у овој релацији.
Број компоненти повезаности уреди
Број компоненти повезаности је важна тополошка инваријанта графа. У тополошкој теорији графова, број компоненти повезаности може да се интерпретира као нулти Бетијев број графа. У алгебарској теорији графова број компоненти повезаности је једнак вишеструкости 0 као сопствени вектор од графа Лапласове матрице. Такође је и индекс првог коефицијента различитог од нуле од хроматског полинома графа. Број компоненти повезаности играју кључну улогу у Тутовој теореми карактеришући графове који имају савршено поклапање, и у дефиницији тежине графова.
Алгоритми уреди
Једноставно је да се израчунају компоненте повезаности графа у линеарном времену (у погледу броја чворова и путева графа) коришћењем било претраге у ширину или претраге у дубину. У било ком случају, претрага која почиње у неком одређеном чвору v пронаћи ће целокупну повезану компоненту која садржи v (и не више) пре повратка. Да бисмо пронашли све повезане компоненте графа, идемо петљом кроз чворове, започињући нову претрагу у ширину или дубину кад год петља достигне чвор који већ није укључен у претходно пронађеној компоненти повезаности. Хопкрофт и Тарџан (1973))[1] описују овај алгоритам у суштини, и наводе да је у том тренутку било „добро познато“.
Постоје и ефикасни алгоритми за динамичко праћење повезаних компоненти графа док се чворови и гране додају, као једноставна примена система дисјунктних структура података. Ови алгоритми захтевају амортизовано O(α(n)) време операције, код којих додајући чворове и путеве, и одређивање повезане компоненте, где су обе операција, и α(n) је врло споро растућа инверзна, од врло брзо растуће Акерманове функције. Сличан проблем представља праћење повезаних компоненти док се све гране бришу из графа, једна по једна; постоји алгоритам за решавање овог константног времена по упиту, и O(|V||E|) време да се одржи структура података; ово је амортизована цена од O(|V|) по брисању пута. За дрвета, цена може да се смањи до O(q + |V| log |V|), или O(log |V|) амортизована цена по обрисаном путу.[2]
Истраживачи су такође проучавали алгоритме за проналажење повезујућих компоненти у више ограниченим моделима рачунања, као што су програми у којима је радна меморија ограничена на логаритамски број битова (дефинисана комплексном класом L). Левис и Пападимитроу (1982) су се питали да ли је могуће да се тестира у логаритамском простору да ли два чвора припадају истој компоненти повезаности неког неусмереног графа, и дефинисали су комплексност SL класе проблема где је логаритамски простор једнак повезаности. Коначно је Реинголд (2008) успео да пронађе алгоритам за решавање овог проблема повезивања у логаритамског простору, показујући да је L = SL.
Референце уреди
- ^ Hopcroft, J.; Tarjan, R. (1973). „Efficient algorithms for graph manipulation”. Communications of the ACM. 16 (6): 372—378. doi:10.1145/362248.362272.
- ^ Shiloach, Y. and Even, S. 1981. An On-Line Edge-Deletion Problem. Journal of the ACM: 28, 1 (Jan. 1981), pp.1-4.
Литература уреди
- Lewis, Harry R.; Papadimitriou, Christos H. (1982), „Symmetric space-bounded computation”, Theoretical Computer Science, 19 (2): 161—187, doi:10.1016/0304-3975(82)90058-5.
- Reingold, Omer (2008), „Undirected connectivity in log-space”, Journal of the ACM, 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291.
Спољашње везе уреди
- Connected components, Steven Skiena, The Stony Brook Algorithm Repository