Отношение связности, компоненты связности — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 4 участников)
Строка 29: Строка 29:
 
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.
 
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.
 
=== Слабая связность ===
 
=== Слабая связность ===
<wikitex>{{Определение
+
{{Определение
 
|definition=
 
|definition=
 
Отношение $R(v, u)$ называется отношением '''слабой связности''' ''(англ. weak connectivity)'', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.
 
Отношение $R(v, u)$ называется отношением '''слабой связности''' ''(англ. weak connectivity)'', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.
Строка 38: Строка 38:
 
Слабая связность '''является [[Отношение_эквивалентности|отношением эквивалентности]]'''.
 
Слабая связность '''является [[Отношение_эквивалентности|отношением эквивалентности]]'''.
 
|proof=
 
|proof=
я хочу пиццы
+
Аналогично доказательству соответствующей теоремы для неориентированного графа.
 
}}
 
}}
 
[[Файл:components1.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами слабой связности.]]
 
[[Файл:components1.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами слабой связности.]]
 
<br clear="all" />
 
<br clear="all" />
</wikitex>
 
  
 
=== Сильная связность ===
 
=== Сильная связность ===
Строка 62: Строка 61:
 
|definition=
 
|definition=
 
Пусть <tex>G = (V, E)</tex> — [[Основные_определения_теории_графов|ориентированный граф]]. '''Компонентой сильной связности''' ''(англ. strongly connected component)'' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}
 
Пусть <tex>G = (V, E)</tex> — [[Основные_определения_теории_графов|ориентированный граф]]. '''Компонентой сильной связности''' ''(англ. strongly connected component)'' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}
 +
Компоненты сильной связности могут быть найдены [[Использование обхода в глубину для поиска компонент сильной связности|с помощью обхода в глубину]].
 
[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]]
 
[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]]
 
{{Определение
 
{{Определение

Текущая версия на 19:30, 4 сентября 2022

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

Определение:
Две вершины [math]u[/math] и [math]v[/math] называются связанными (англ. adjacent), если в графе [math]G[/math] существует путь из [math]u[/math] в [math]v[/math] (обозначение: [math]u \rightsquigarrow v [/math]).


Теорема:
Связность — отношение эквивалентности (англ. equivalence relation).
Доказательство:
[math]\triangleright[/math]

Рефлексивность: [math]\forall a \in V a \rightsquigarrow a[/math] (очевидно).

Симметричность: [math]a\rightsquigarrow b \Rightarrow b\rightsquigarrow a[/math] (в силу неориентированности графа).

Транзитивность: [math]a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c[/math]. Действительно, сначала пройдем от [math]a[/math] до [math]b[/math], затем от [math]b[/math] до [math]c[/math], что и означает существования пути [math]a \rightsquigarrow c[/math].
[math]\triangleleft[/math]


Определение:
Компонентой связности (англ. connected component) называется класс эквивалентности относительно связности.


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


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

В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.

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

Определение:
Отношение $R(v, u)$ называется отношением слабой связности (англ. weak connectivity), если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.


Теорема:
Слабая связность является отношением эквивалентности.
Доказательство:
[math]\triangleright[/math]
Аналогично доказательству соответствующей теоремы для неориентированного графа.
[math]\triangleleft[/math]
Пример ориентированного графа с тремя компонентами слабой связности.


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

Определение:
Отношение [math]R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v[/math] на вершинах графа называется отношением сильной связности (англ. strong connectivity).


Теорема:
Сильная связность — отношение эквивалентности.
Доказательство:
[math]\triangleright[/math]

Рефлексивность и симметричность очевидны. Рассмотрим транзитивность:

[math](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[/math]
[math]\triangleleft[/math]


Определение:
Пусть [math]G = (V, E)[/math]ориентированный граф. Компонентой сильной связности (англ. strongly connected component) называется класс эквивалентности множества вершин этого графа относительно сильной связности.

Компоненты сильной связности могут быть найдены с помощью обхода в глубину.

Пример ориентированного графа с тремя компонентами сильной связности.
Определение:
Ориентированный граф [math]G = (V, E)[/math] называется сильно связным (англ. strongly connected), если он состоит из одной компоненты сильной связности.



См. также

Источники информации