69
правок
Изменения
Нет описания правки
== Случай неориентированного графа ==
=== Компоненты связности Связность ===
{{Определение
|definition=
'''Транзитивность''': <math>a\rightsquigarrow b \and b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</math> (Очевидно)
}}
{{Определение
|definition=
== Случай ориентрованного графа ==
В общем случае для ориентированного графа существование пути — нетранзитивное отношение, поэтому вместо понятия связность различают понятие слабой и сильной связности
=== Слабая связность ===
{{Определение
|definition=
Пусть <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> }}
{{Определение
|definition=
Пусть <math>G = (V, E)</math> — ориентированный граф. '''Компонента слабой связности''' - класс эквивалентности вершин графа <math>C_i</math>, на которые разбивает множество <math>V</math> отношение существования неориентированного пути}}
{{Определение
|definition=
Ориентированный граф <math>G = (V, E)</math> называется '''слабо связным''' если он состоит из одной компоненты слабой связности }}
=== Сильная связность ===
Пусть <math>G=(V, E) </math> — ориентированный граф. Введем отношение на вершинах графа: <math>R(v, u) = v \rightsquigarrow u \and u \rightsquigarrow v</math>. Очевидно, <math>R</math> рефлексивно, коммутативно, транзитивно.
{{Определение
|definition=
Пусть <math>G = (V, E)</math> — ориентированный граф. '''Компонента сильной связности''' - класс эквивалентности вершин графа <math>C_i</math>, на которые разбивает множество <math>V</math> отношение существования пути между вершинами в обе стороны}}
{{Определение
|definition=
Ориентированный граф <math>G = (V, E)</math> называется '''сильно связным''' если он состоит из одной компоненты сильной связности}}
