Čvrsta komponenta povezanosti
| Ovaj članak je započet ili proširen kroz projekat seminarskih radova. Potrebno je proveriti prevod, pravopis i viki-sintaksu. Kada završite sa proverom, dopišete da nakon |provereno=. |
Usmereni graf je čvrsto povezan ukoliko postoji put od svakog čvora u grafu do svakog drugog čvora. Konkretno, to znači da postoje putevi u svakom smeru; put od a do b, a takođe, put od b do a.
Čvrste komponente povezanosti usmerenog grafa G su njegovi maksimalno čvrsto povezani podgrafi. Ako je svaka čvrsto povezana komponenta identifikovana sa jednim čvorom, rezultat je usmereni aciklični graf, kondenzacije G. Usmereni graf je acikličan ako i samo ako nema čvrsto povezane podgrafe sa više od jednog čvora, zato što je usmereni ciklus čvrsto povezan i svaka netrivijalna čvrsto povezana komponenta sadrži bar jedan usmereni ciklus.
Kosarajuov algoritam, Tardžanov algoritam i Algoritam za nalaženje čvrsto povezanih komponenti grafa, efikasno izračunavaju čvrsto povezane komponente usmerenog grafa, ali Tardžanov i čvrsto povezujući algoritam su favorizovani u praksi, jer zahtevaju samo jednu prvu pretragu u dubinu, a ne dve.
Algoritmi za pronalaženje čvrsto povezanih komponenti mogu da se koriste za rešavanje problema 2-SAT (sistemi Bulovih promenljivih sa ograničenjima o vrednostima parova promenljivih): kao što su Apsval, Plas i Tardžan (1979) pokazali, 2-SAT primer je nezadovoljiv ako i samo ako postoji promenljiva v tako da se v i njen komplement zajedno nalaze u istoj čvrsto povezanoj komponenti od implikacije grafa primera.
Prema Robinsovoj teoremi, neusmeren graf može biti orijentisan na takav način da on postaje čvrsto povezan, ako i samo ako je na dve grane povezan.
Literatura uredi
- 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.
Spoljašnje veze uredi
- Java implementation for computation of strongly connected components in the jBPT library (see StronglyConnectedComponents class).