Материал из Викиконспекты
Случай неориентированного графа
Определение: |
Две вершины [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), если он состоит из одной компоненты связности. В противном случае граф называется несвязным. |
Случай ориентированного графа
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.
Слабая связность
<wikitex>
Определение: |
Отношение $R(v, u)$ называется отношением слабой связности (weak connectivity), если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением с ребер ориентации. |
Теорема: |
Слабая связность является отношением эквивалентности. |
Доказательство: |
[math]\triangleright[/math] |
Аналогично доказательству соответствующей теоремы для неориентированного графа. |
[math]\triangleleft[/math] |
Пример ориентированного графа с тремя компонентами слабой связности.
</wikitex>
Сильная связность
Определение: |
Отношение [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] — ориентированный граф. Компонентой сильной связности называется класс эквивалентности множества вершин этого графа относительно сильной связности. |
Пример ориентированного графа с тремя компонентами сильной связности.
Определение: |
Ориентированный граф [math]G = (V, E)[/math] называется сильно связным, если он состоит из одной компоненты сильной связности. |
Источники