355
правок
Изменения
→Слабая связность
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.
=== Слабая связность ===
<wikitex>{{Определение
|definition=
Отношение <tex>$R(v, u) = v \rightsquigarrow u \lor u \rightsquigarrow v</tex> на вершинах графа $ называется отношением '''слабой связности''', если вершины $u$ и $v$ связаны в графе $G'$, полученном из графа $G$ снятием с ребер ориентации.
}}
{{Утверждение
|statement=
Слабая связность '''не является отношением эквивалентности'''.
|proof=
Достаточно показать, что оно не '''транзитивно''': <tex>a\rightsquigarrow b \land c\rightsquigarrow b \not\Rightarrow a\rightsquigarrow c</tex>.
}}
</wikitex>
=== Сильная связность ===
