Связность графа. 
Математическая обработка информации

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

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

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

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

Пусть G = (X, А) — неориентированный граф с множеством вершин X = {.г, х"). Квадратная матрица S = (s_{/).

порядка п, у которой:

• • Sy = 1, если вершины и принадлежат одной компоненте связности;
• • Sjj = 0 в противном случае называется матрицей связности графа G.

Для ориентированного графа квадратная матрица Т = (tjj) порядка п, у которой:

• • ty = 1, если существует путь из х,? в xf,
• • ty = 0 в противном случае называется матрицей связности.

Пример 3.10. У неориентированного графа, изображенного на рис. 3.28 (табл. 3.7), две компоненты связности. Первая компонента связности включает вершины х_{, х₂, х_А,а вторая состоит из одной вершины x_:i.

Рис. 3.28. Неориентированный граф с двумя компонентами связности (пример 3.10)

Таблица 3.7

Матрица связности S неориентированного графа (рис. 3.28)

Пример 3.11. У ориентированного графа, изображенного на рис. 3.29 (табл. 3.8), две компоненты сильной связности. Первая компонента связности включает вершины x_v х₂, х₃, х₅, а вторая состоит из одной вершины х₄. Действительно, для любой пары вершин из множества {x_v х₂, х₃, х₅} существует хотя бы один путь, соединяющий эти вершины. Например, путь (x_vх₂, х₅, х₃>х_{) соединяет все эти вершины. Из вершины х₄ нет пути ни в одну вершину графа.

Рис. 3.29. Ориентированный граф с двумя компонентами связности (пример 3.11).

Таблица 3.8

Матрица связности Ториентированного графа (рис. 3.29).

Мы видим, что строки 1, 2, 3 и 5 матрицы Тодинаковы.