Компоненте повезаности (теорија графова)
У теорији графова, повезана компонента неусмереног графа је подграф у ком су било која два чвора међусобно повезана путевима, и који није повезан са додатним чворовима у суперграфу. На пример, у графу приказаном на илустрацији са десне стране се налазе три повезане компоненте. Граф које је повезан сам са собом, има тачно једну повезану компоненту, чинећи цео граф.
Релација еквиваленције[уреди | уреди извор]
Алтернативни начин да се дефинише повезана компонента укључује класе еквиваленције од релације еквиваленције која је дефинисана на чворовима графа. У неусмереном графу, чвор 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