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

Из Википедије, слободне енциклопедије
Граф са три повезане компоненте.

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

Релација еквиваленције[уреди]

Алтернативни начин да се дефинише повезана компонента укључује класе еквиваленције од релације еквиваленције која је дефинисана на чворовима графа. У неусмереном графу, чвор 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.

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

  1. ^ Hopcroft, J.; Tarjan, R. (1973). „Efficient algorithms for graph manipulation“. Communications of the ACM 16 (6): 372–378. DOI:10.1145/362248.362272. 
  2. ^ Shiloach, Y. and Even, S. 1981. An On-Line Edge-Deletion Problem. Journal of the ACM: 28, 1 (Jan. 1981), pp.1-4.

Литература[уреди]

Спољашње везе[уреди]