3.3 Компоненты связности и сильной связности

 

Граф (M, N, T) называется связным, если любые две различных его вершины можно соединить цепью. Любой граф может быть однознач­но разделен на максимальные связные подграфы, которые называют­ся его компонентами связности. Число различных компонент связности графа называется его числом связности.

Пример 1. Граф, изображенный на рис.7, состоит из трех компонент связности.

Рис. 7. Пример несвязного графа.

 

Граф (M, N, T) называется сильно связным, если любые две раз­личные его вершины i1 и i2 можно соединить путем с началом i1 и концом i2. В любом графе можно однозначно выделить максималь­ные сильно связные подграфы, которые называются его компонента­ми сильной связности. Число различных компонент сильной связности графа называется его числом сильной связности. Число сильной связности графа, изображенного на рис. 7 равно 9.