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

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

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

Две вершины [math]u[/math] и [math]v[/math] называются связными, если в графе [math]G[/math] существует путь из [math]u[/math] в [math]v[/math].

Теорема:

Связность - отношение эквивалентности.

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

[math]\triangleright[/math]

Рефлексивность: [math]\forall a \in V a \rightsquigarrow a[/math] (очевидно). Симметричность: [math]a\rightsquigarrow b \Rightarrow b\rightsquigarrow a[/math] (в силу неориентированности графа). Транзитивность: [math]a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c[/math]. Действительно, сначала пройдем от [math]a[/math] до [math]b[/math], затем от [math]b[/math] до [math]c[/math], что и означает существования пути [math]u \rightsquigarrow v[/math].

[math]\triangleleft[/math]

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

Компонентой связности называется класс эквивалентности относительно связности.

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

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

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

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

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

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

Две вершины [math]u[/math] и [math]v[/math] называются слабо связными, если [math]\exists u \rightsquigarrow v \lor \exists u \rightsquigarrow v[/math]

Утверждение:

Слабая связность - не является отношением эквивалентности.

[math]\triangleright[/math]

Достаточно показать, что оно не транзитивно: [math]a\rightsquigarrow b \land c\rightsquigarrow b \not\Rightarrow a\rightsquigarrow c[/math].

[math]\triangleleft[/math]

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

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

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

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

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

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