Изменения

Перейти к: навигация, поиск

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

423 байта добавлено, 07:04, 18 октября 2011
→‎Случай ориентированного графа
{{Определение
|definition=
Две вершины <tex>u</tex> и Отношение <tex>R(v</tex> называются '''слабо связными''', если <tex>\exists u ) = v \rightsquigarrow v u \lor \exists u \rightsquigarrow v</tex>на вершинах графа называется отношением '''слабой связности'''.
}}
{{Утверждение
|statement=
Слабая связность - '''не является отношением эквивалентности'''.
|proof=
Достаточно показать, что оно не '''транзитивно''': <tex>a\rightsquigarrow b \land c\rightsquigarrow b \not\Rightarrow a\rightsquigarrow c</tex>.
=== Сильная связность ===
Пусть <tex>G=(V, E) </tex> — ориентированный граф. Введем отношение на вершинах графа: <tex>R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v</tex>. Очевидно, <tex>R</tex> рефлексивно, коммутативно, транзитивно.
{{Определение
|definition=
Пусть Отношение <tex>G = R(Vv, Eu)= v \rightsquigarrow u \land u \rightsquigarrow v</tex> — ориентированный граф. на вершинах графа называется отношением '''Компоненты сильной связности''' — классы .}} {{Теорема|statement=Сильная связность - '''отношение эквивалентности вершин графа '''.|proof='''Рефлексивность''' и '''симметричность''' очевидны. Рассмотрим '''транзитивность''': <tex>C_i(a\rightsquigarrow b \land b\rightsquigarrow a) \land (b\rightsquigarrow c \land c\rightsquigarrow b)\Leftrightarrow (a\rightsquigarrow b \land b\rightsquigarrow c) \land (c\rightsquigarrow b \land b\rightsquigarrow a) \Leftrightarrow a\rightsquigarrow c \land c\rightsquigarrow a</tex>, на которые разбивает множество }} {{Определение|definition=Пусть <tex>G = (V, E)</tex> отношение существования пути между вершинами в обе стороны— ориентированный граф. '''Компонентой сильной связности''' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}
{{Определение
|definition=
Ориентированный граф <tex>G = (V, E)</tex> называется '''сильно связным''', если он состоит из одной компоненты сильной связности.}}
Smolcoder
355
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/11370»

Навигация