Чврста компонента повезаности

Из Википедије, слободне енциклопедије
Jump to navigation Jump to search
Маркиран је граф са чврсто повезаним компонентама

Усмерени граф је чврсто повезан уколико постоји пут од сваког чвора у графу до сваког другог чвора. Конкретно, то значи да постоје путеви у сваком смеру; пут од а до b, а такође, пут од b до а.

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

Косарајуов алгоритам, Тарџанов алгоритам и Алгоритам за налажење чврсто повезаних компоненти графа, ефикасно израчунавају чврсто повезане компоненте усмереног графа, али Тарџанов и чврсто повезујући алгоритам су фаворизовани у пракси, јер захтевају само једну прву претрагу у дубину, а не две.

Алгоритми за проналажење чврсто повезаних компоненти могу да се користе за решавање проблема 2-SAT (системи Булових променљивих са ограничењима о вредностима парова променљивих): као што су Апсвал, Плас и Тарџан (1979) показали, 2-SAT пример је незадовољив ако и само ако постоји променљива v тако да се v и њен комплемент заједно налазе у истој чврсто повезаној компоненти од импликације графа примера.

Према Робинсовој теореми, неусмерен граф може бити оријентисан на такав начин да он постаје чврсто повезан, ако и само ако је на две гране повезан.

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

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