Отношение связности, компоненты связности

Случай неориентированного графа

Связность

Определение:

Компоненты связности неориентированного графа $G=(V, E)$ — такие множества $C_i$ что $C_i \subset V$ и между любыми вершинами из одного множества существует путь., а между любыми вершинами из разных множеств не существует пути

Теорема:

Для неориентированного графа $G=(V, E)$ cемейство множеств $C_i$ удовлетворяющих определению единственно и образует разбиение множества $V$

Доказательство:

$\triangleright$

Докажем что отношение существования пути, заданное на множестве вершин графа, разбивает множество $V$ на классы эквивалентности Рефлексивность: $\forall a \in V a \rightsquigarrow a$ (Очевидно) Коммутативность: $a\rightsquigarrow b \Rightarrow b\rightsquigarrow a$ (В силу неориентированности графа) Транзитивность: $a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c$ (Очевидно)

$\triangleleft$

Определение:

Граф $G=(V, E)$ называется связным если он состоит из одной компоненты связности. В противном случае граф называется несвязным

Случай ориентированного графа

В общем случае для ориентированного графа существование пути — нетранзитивное отношение, поэтому вместо понятия связность различают понятие слабой и сильной связности

Слабая связность

Определение:

Пусть $G = (V, E)$ — ориентированный граф. Рассмотрим граф $G' = (V, E')$, составленный из вершин графа $G$, в котором ребро $(x, y)$ существует тогда и только тогда когда $(x, y) \in E \lor (y, x) \in E$ Скажем что между вершинами $v \in G$ и $u \in G$ существет неориентированный путь если $v$ и $u$ связаны путем в $G'$

Определение:

Пусть $G = (V, E)$ — ориентированный граф. Компонента слабой связности - класс эквивалентности вершин графа $C_i$, на которые разбивает множество $V$ отношение существования неориентированного пути

Определение:

Ориентированный граф $G = (V, E)$ называется слабо связным если он состоит из одной компоненты слабой связности

Сильная связность

Пусть $G=(V, E)$ — ориентированный граф. Введем отношение на вершинах графа: $R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v$. Очевидно, $R$ рефлексивно, коммутативно, транзитивно.

Определение:

Пусть $G = (V, E)$ — ориентированный граф. Компонента сильной связности - класс эквивалентности вершин графа $C_i$, на которые разбивает множество $V$ отношение существования пути между вершинами в обе стороны

Определение:

Ориентированный граф $G = (V, E)$ называется сильно связным если он состоит из одной компоненты сильной связности