Силно свързан компонент в диграф
Диграф се наричасилно свързан, ако всеки два от неговите върхове са силно свързани. Два върха s и t на всеки граф са силно свързани, ако има насочен път от s към t и насочен път от t към s.Силно свързаните компонентина орграф са неговите максимални за включване силно свързани подграфи.Силно свързан регионе набор от върхове на силно свързан компонент.
Съдържание
Орграф, който не принадлежи към класа на силно свързаните графи, съдържа някакъв набор отсилно свързани компонентии някакъв набор от насочени ребра, преминаващи от един компонент към друг.
Всеки връх на орграф е силно свързан със себе си.
Най-простият алгоритъм за решаване на проблема за намиране на силно свързани компоненти в диграф работи по следния начин:
- Използвайки транзитивно затваряне, ние проверяваме дали t е достижимо от s и s от t за всички двойки от s и t.
- След това дефинираме такъв неориентиран граф, който съдържа ребро за всяка такава двойка.
- Намирането на свързаните компоненти на такъв неориентиран граф ще ни даде силно свързаните компоненти на нашия орграф.
Очевидно основното време на работа на този алгоритъм пада върху прилагането на транзитивно затваряне.
Има и три алгоритъма, които решават този проблем за линейно време, тоест V пъти по-бързо от горния алгоритъм. Това са алгоритмите на Косараю, Гъбов и Тарян.
Този пример показва диграф, за който са намерени и трите силно свързани компонента (запълнени области, оградени с пунктирана линия).