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

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

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

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

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

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

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

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

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