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

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

Компоненты связности

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

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

Теорема:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Связность

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

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

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

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

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

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