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

Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу.
Када завршите са провером, допишете да након |проверено=.

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

Маркиран је граф са чврсто повезаним компонентама

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

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

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

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

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

Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), „A linear-time algorithm for testing the truth of certain quantified boolean formulas”, Information Processing Letters, 8 (3): 121—123, doi:10.1016/0020-0190(79)90002-4 .
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, (2001) ISBN 978-0-262-03293-3. Section 22.5, pp. 552-557.

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

Java implementation for computation of strongly connected components in the jBPT library (see StronglyConnectedComponents class).