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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Сильная связность)
(Слабая связность)
Строка 37: Строка 37:
 
Аналогично доказательству соответствующей теоремы для неориентированного графа.
 
Аналогично доказательству соответствующей теоремы для неориентированного графа.
 
}}
 
}}
 +
[[Файл:Слаб.png|frame|слева|Слабосвязный граф. Компоненты слабой связности выделены красным.]]
 +
<br clear="all" />
 
</wikitex>
 
</wikitex>
  

Версия 22:00, 22 октября 2011

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

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


Теорема:
Связность - отношение эквивалентности.
Доказательство:
[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 b[/math].
[math]\triangleleft[/math]


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


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


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

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

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

<wikitex>

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


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


</wikitex>

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

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


Теорема:
Сильная связность - отношение эквивалентности.
Доказательство:
[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] — ориентированный граф. Компонентой сильной связности называется класс эквивалентности множества вершин этого графа относительно сильной связности.


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


Сильносвязный граф. Компоненты сильной связности выделены красным.


Источники

  • ivtb.ru
  • Харари Фрэнк Теория графов: Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.