Изменения

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

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

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

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

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

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

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

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

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

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