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

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