7. Сильно связные графы и компоненты графа

Ориентированный граф называется сильно связным или сильным, если для любых двух различных вершин существует по крайней мере один путь, соединяющий Это определение означает также, что любые две вершины такого графа взаимно достижимы.

Ориентированный граф называется односторонне связным или односторонним, если для любых двух различных вершин существует по крайней мере один путь из или из (или оба одновременно).

Ориентированный граф называют слабо связным или слабым, если для любых двух различных вершин графа существует по крайней мере один маршрут, соединяющий их.

Если для некоторой пары вершин орграфа не существует маршрута, соединяющего их, то такой орграф называется несвязным [2].

Граф, приведенный на рис. 1.7(a), как легко проверить, сильно связный. Граф, показанный на рис. 1.7(6), не является сильным (так как в нем нет пути из но односторонне связный. Граф, изображенный на рис. не является ни сильным, ни односторонним, поскольку в нем не существует путей от и от Он — слабо связный. Наконец, граф, приведенный на рис. 1.7(г), является несвязным.

Пусть дано некоторое свойство которым могут обладать графы. Максимальным подграфом графа относительно свойства

Р называется порожденный подграф графа обладающий этим свойством и такой, что не существует другого порожденного подграфа которого и который также обладает свойством

Рис. 1.7. (а) Сильно связный граф. (б) Односторонне связный граф. (в) Слабо связный граф. (г) Несвязный граф.

Так, например, если в качестве свойства взята сильная связность, то максимальным сильным подграфом графа является сильный подграф, который не содержится в любом другом сильном подграфе. Такой подграф называется сильной компонентой графа Аналогично, односторонняя компонента представляет собой односторонний максимальный подграф, а слабая компонента — максимальный слабый подграф.

Например, в графе приведенном на рис. подграф является сильной компонентой графа С другой стороны, подграфы не являются сильными компонентами (хотя и являются сильными подграфами), поскольку они содержатся в графе следовательно, не максимальные. В графе, показанном на рис. 1.7(b), подграф является односторонней компонентой. В графе, приведенном рис. 1.7(г), оба подграфа являются слабыми компонентами, и у этого графа только две такие компоненты.

Из определений сразу же следует, что односторонние компоненты графа могут иметь общие вершины. Сильная компонента должна содержаться по крайней мере в одной односторонней компоненте, а односторонняя компонента содержится в некоторой слабой компоненте данного графа