1. Компоненты графа
Ориентированный граф (орграф) называется сильно связным, если для любых двух различных вершин хi и xj существует, по крайней мере, один путь, соединяющий хi с хj.
В таком графе любые две вершины взаимно достижимы.Орграф называется односторонне связным, если для любых двух различных вершин хi и xj существует, по крайней мере, один путь из хi в хj или из xj в хi или оба одновременно.
Орграф называют слабо связным, если для любых двух различных вершин графа существует, по крайней мере, один маршрут (неориентированный двойник пути), соединяющий их.
Если для некоторой пары вершин орграфа не существует маршрута соединяющего их, то такой орграф называется несвязным.
Максимальным сильным подграфом графа G является сильно связный подграф, который не содержится в любом другом сильно связном подграфе. Такой подграф называется сильной компонентой графа G. Аналогично, односторонняя компонента представляет собой односторонне связный максимальный подграф, а слабая компонента - максимальный слабо связный подграф.
Сильная компонента содержится, по крайней мере, в одной односторонней компоненте, а односторонняя компонента содержится в некоторой слабой компоненте G, так как односторонние компоненты графа могут иметь общие вершины.
Например, в односторонне связном графе G, приведенном на рис. 1.1, порожденные подграфы , и являются сильно связными подграфами, а подграф является сильной компонентой графа G.
Рис. 1.1. Ориентированный граф G.