Орієнтований граф називається сильно зв'язним, якщо існує шлях з будь-якої вершини графа до кожної з інших вершин. Зокрема, це означає наявність шляхів в обох напрямках: з a в b і з b в a.
Компонента сильної зв'язності орієнтованого графа G — це найбільший сильно зв'язаний підграф. Якщо кожну компонента сильної зв'язності стягнути до однієї вершини, отримаємо орієнтований ациклічний граф, ущільнення (англ. condensation) G. Орієнтований граф є ациклічним тоді і лише тоді, коли він не має компонент сильної зв'язності з більш як однією вершиною, бо орієнтований цикл є сильно зв'язним і кожна нетривіальна компонента сильної зв'язності містить щонайменше один орієнтований цикл.
Алгоритм Косараджу, алгоритм Тар'яна і всі дієво знаходять компоненти сильної зв'язності орієнтованого графа, але алгоритм Тар'яна і алгоритм базований на шляхах сприятливіші на практиці, бо вони потребують лише один пошук у глибину замість двох.
Відповідно до теореми Роббінса, неорієнтований граф можна зорієнтувати таким чином, що він стане сильно зв’язним, тоді і тільки тоді, коли він 2-реберно-зв'язний.
Див. також
Джерела
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 22.5: Компоненти сильнї зв'язності. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Oriyentovanij graf nazivayetsya silno zv yaznim yaksho isnuye shlyah z bud yakoyi vershini grafa do kozhnoyi z inshih vershin Zokrema ce oznachaye nayavnist shlyahiv v oboh napryamkah z a v b i z b v a Graf z poznachenimi komponentami silnoyi zv yaznosti Komponenta silnoyi zv yaznosti oriyentovanogo grafa G ce najbilshij silno zv yazanij pidgraf Yaksho kozhnu komponenta silnoyi zv yaznosti styagnuti do odniyeyi vershini otrimayemo oriyentovanij aciklichnij graf ushilnennya angl condensation G Oriyentovanij graf ye aciklichnim todi i lishe todi koli vin ne maye komponent silnoyi zv yaznosti z bilsh yak odniyeyu vershinoyu bo oriyentovanij cikl ye silno zv yaznim i kozhna netrivialna komponenta silnoyi zv yaznosti mistit shonajmenshe odin oriyentovanij cikl Algoritm Kosaradzhu algoritm Tar yana i vsi diyevo znahodyat komponenti silnoyi zv yaznosti oriyentovanogo grafa ale algoritm Tar yana i algoritm bazovanij na shlyahah spriyatlivishi na praktici bo voni potrebuyut lishe odin poshuk u glibinu zamist dvoh Vidpovidno do teoremi Robbinsa neoriyentovanij graf mozhna zoriyentuvati takim chinom sho vin stane silno zv yaznim todi i tilki todi koli vin 2 reberno zv yaznij Div takozhKomponenta zv yaznosti grafa Faktor grafDzherelaT Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 Rozdil 22 5 Komponenti silnyi zv yaznosti Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4