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

Кроме классификации типов графов данной в п. 2.2 графы могут быть классифицированы по связности: сильно связные, односторонне связные, слабо связные и несвязные.

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

Виды графов по связности (рис. 11): а – cильно связный граф; б – односторонне связный граф; в – cлабо связный граф; г – несвязный граф

Рисунок 11

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

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

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

По признаку связности могут быть классифицированы и подграфы, но сначала введем понятие максимального подграфа. Пусть дано некоторое свойство Р, которым могут обладать графы.

Максимальным подграфом графа G относительно свойства Р называется порожденный подграф G_sm , обладающий этим свойством и такой, что не существует другого порожденного графа G_s , у которого V_s⊃V_sm и который так же обладает свойством Р. Так, например, если в качестве свойства Р взята сильная связанность, то максимальным сильным подграфом графа G является сильный подграф, который не содержится ни в каком другом сильном подграфе. Такой подграф называется сильной компонентой графа. Аналогично, односторонняя компонента представляет собой односторонний максимальный подграф, а слабая компонента – максимальный слабый подграф.

Например, в графе, приведенном на рис. 11,б, подграф, состоящий из вершин{х₁, х₄, х₅, х₆}, является сильной компонентой графа. С другой стороны подграфы, включающие вершины {х₁, х₆} и {х₁, х₅, х₆}, не являются сильными компонентами (хотя и являются сильными подграфами), поскольку они содержатся в графе, состоящем из вершин {х₁, х₄, х₅, х₆} и, следовательно, не максимальные. В графе, показанном на рис. 11,в, подграф не содержит вершины {х₁, х₄, х₅, х₆}, является односторонней компонентой.

В графе, приведенном на рис. 11,г, оба подграфа, включающие вершины {х₁, х₅, х₆} и {х₂, х₃, х₄} являются слабыми компонентами, и у этого графа только две компоненты.

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