Связность графа, сильно связный граф

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

Две вершины v и w графа называются связными, если существует соединяющая их цепь. Если же в графе нет ни одной цепи, соединяющей вершины v и w, то вершины v и w являются несвязными.

Например, вершины 1 и 5 (рис. 3) связны, так как их соединяет цепь 1, 7, 6, 5 (а так-же 1, 7, 2, 5; 1, 7, 6, 2, 5 и 1, 7, 2, 6, 5), а вершины 2 и 3 связными не являются, так как ни одна цепь их не соединяет.

Граф называется связным, если каждые две его вершины связны. Если же в графе имеется хотя бы одна пара вершин, не соединенных цепью, то граф называется несвязным. Согласно этим определениям граф, изображенный на рис. 2, является связным, а граф, приведенный на рис. 3, – несвязным.

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

Число компонент, из которых состоит граф, называется степенью связности. Граф, изображенный на рис. 3, имеет степень связности, равную 2.

В ориентированных графах различают несколько понятий связности.

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

Ориентированный граф называется слабо-связным, если является связным неориентированный граф, полученный из него заменой ориентированных рёбер неориентированными.

Здесь приведены некоторые критериальные (эквивалентные) определения связного графа:
Граф называется односвязным (связным), если:

1. У него одна компонента связности

2. Существует путь из любой вершины в любую другую вершину

3. Существует путь из заданной вершины в любую другую вершину

4. Содержит связный подграф, включающий все вершины исходного графа

5. Содержит в качестве подграфа дерево, включающее все вершины исходного графа (такое дерево называется остовным)

6. При произвольном делении его вершин на 2 группы всегда существует хотя бы 1 ребро, соединяющее пару вершин из разных групп