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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 63 промежуточные версии 22 участников)
Строка 1: Строка 1:
 
== Случай неориентированного графа ==
 
== Случай неориентированного графа ==
−
=== Связность ===
+
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Компоненты связности''' неориентированного [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл|графа]] <tex>G=(V, E)</tex> — такие множества <tex>C_i</tex>, что <tex>C_i \subset V</tex>, и между любыми вершинами из одного множества существует [[Основные определения: граф, ребро, вершина, степень, петля, путь, цикл#Путь|путь]], а между любыми вершинами из разных множеств — нет.}}
+
Две вершины <tex>u</tex> и <tex>v</tex> называются '''связанными''' ''(англ. adjacent)'', если в графе <tex>G</tex> существует [[Основные определения теории графов|путь]] из <tex>u</tex> в <tex>v</tex> (обозначение: <tex>u \rightsquigarrow v </tex>).}}
  
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
−
Для неориентированного графа <tex>G=(V, E)</tex> cемейство множеств <tex>C_i</tex>, удовлетворяющих определению, единственно и образует разбиение множества <tex>V</tex>.
+
Связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]''' ''(англ. equivalence relation)''.
 
|proof=
 
|proof=
−
Докажем, что отношение существования пути, заданное на множестве вершин графа, разбивает множество <tex>V</tex> на '''классы эквивалентности'''.
+
'''[[Рефлексивное_отношение|Рефлексивность]]''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно).
  
−
'''Рефлексивность''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно).
+
'''[[Симметричное_отношение|Симметричность]]''': <tex>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</tex> (в силу неориентированности графа).
  
−
'''Симметричность''': <tex>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</tex> (в силу неориентированности графа).
+
'''[[Транзитивное_отношение|Транзитивность]]''': <tex>a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</tex>. Действительно, сначала пройдем от <tex>a</tex> до <tex>b</tex>, затем от <tex>b</tex> до <tex>c</tex>, что и означает существования пути  <tex>a \rightsquigarrow c</tex>.
 +
}}
  
−
'''Транзитивность''': <tex>a\rightsquigarrow b \land b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</tex> (очевидно).
+
{{Определение
−
}}
+
|id = def2
 +
|definition=
 +
'''Компонентой связности''' ''(англ. connected component)'' называется класс эквивалентности относительно связности.}}
  
 
{{Определение
 
{{Определение
 +
|id = connected_graph
 
|definition=
 
|definition=
−
Граф <tex>G=(V, E)</tex> называется '''связным''', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}}
+
Граф <tex>G=(V, E)</tex> называется '''связным''' ''(англ. connectivity graph)'', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}}
  
 
== Случай ориентированного графа ==
 
== Случай ориентированного графа ==
 
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.
 
В общем случае для ориентированного графа существование пути — не симметричное отношение, поэтому вместо понятия связности различают понятие слабой и сильной связности.
 
=== Слабая связность ===
 
=== Слабая связность ===
−
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Пусть <tex>G = (V, E)</tex> — ориентированный граф. Рассмотрим граф <tex>G' = (V, E')</tex>, составленный из вершин графа <tex>G</tex>, в котором ребро <tex>(x, y)</tex> существует тогда и только тогда, когда <tex>(x, y) \in E \lor (y, x) \in E</tex>. Скажем, что между вершинами <tex>v \in G</tex> и <tex>u \in G</tex> существет '''неориентированный путь''', если <tex>v</tex> и <tex>u</tex> связаны путем в <tex>G'</tex>.}}
+
Отношение $R(v, u)$ называется отношением '''слабой связности''' ''(англ. weak connectivity)'', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.
 +
}}
 +
 
 +
{{Теорема
 +
|statement=
 +
Слабая связность '''является [[Отношение_эквивалентности|отношением эквивалентности]]'''.
 +
|proof=
 +
Аналогично доказательству соответствующей теоремы для неориентированного графа.
 +
}}
 +
[[Файл:components1.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами слабой связности.]]
 +
<br clear="all" />
 +
 
 +
=== Сильная связность ===
 
{{Определение
 
{{Определение
 +
|id=sc_def
 
|definition=
 
|definition=
−
Пусть <tex>G = (V, E)</tex> — ориентированный граф. '''Компоненты слабой связности''' — классы эквивалентности вершин графа <tex>C_i</tex>, на которые разбивает множество <tex>V</tex> отношение существования неориентированного пути.}}
+
Отношение <tex>R(v, u) = v \rightsquigarrow u \land  u \rightsquigarrow v</tex> на вершинах графа называется отношением '''сильной связности''' ''(англ. strong connectivity)''.
−
{{Определение
+
}}
−
|definition=
+
 
−
Ориентированный граф <tex>G = (V, E)</tex> называется '''слабо связным''', если он состоит из одной компоненты слабой связности.}}
+
{{Теорема
 +
|statement=
 +
Сильная связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]'''.
 +
|proof=
 +
'''[[Рефлексивное_отношение|Рефлексивность]]''' и '''[[Симметричное_отношение|симметричность]]''' очевидны. Рассмотрим '''[[Транзитивное_отношение|транзитивность]]''':
 +
<tex>(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>
 +
}}
  
−
=== Сильная связность ===
 
−
Пусть <tex>G=(V, E) </tex> — ориентированный граф. Введем отношение на вершинах графа: <tex>R(v, u) = v \rightsquigarrow u \land  u \rightsquigarrow v</tex>. Очевидно, <tex>R</tex> рефлексивно, коммутативно, транзитивно.
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Пусть <tex>G = (V, E)</tex> — ориентированный граф. '''Компоненты сильной связности''' — классы эквивалентности вершин графа <tex>C_i</tex>, на которые разбивает множество <tex>V</tex> отношение существования пути между вершинами в обе стороны.}}
+
Пусть <tex>G = (V, E)</tex> — [[Основные_определения_теории_графов|ориентированный граф]]. '''Компонентой сильной связности''' ''(англ. strongly connected component)'' называется класс эквивалентности множества вершин этого графа относительно сильной связности.}}
 +
Компоненты сильной связности могут быть найдены [[Использование обхода в глубину для поиска компонент сильной связности|с помощью обхода в глубину]].
 +
[[Файл:Components2.png|400px|thumb|left|Пример ориентированного графа с тремя компонентами сильной связности.]]
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Ориентированный граф <tex>G = (V, E)</tex> называется '''сильно связным''', если он состоит из одной компоненты сильной связности.}}
+
[[Основные_определения_теории_графов|Ориентированный граф]] <tex>G = (V, E)</tex> называется '''сильно связным''' ''(англ. strongly connected)'', если он состоит из одной компоненты сильной связности.}}
 +
 
 +
<br clear="all" />
 +
 
 +
==См. также==
 +
 
 +
*[[Отношение рёберной двусвязности]]
 +
*[[Отношение вершинной двусвязности]]
 +
 
 +
==Источники информации==
 +
* [http://xn--90abr5b.xn--p1ai/wiki/doku.php?id=examination:diskretka:question12 Отношения связности для вершин неорграфа на ivtb.ru]
 +
* Харари Фрэнк '''Теория графов''': Пер. с англ./ Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 296 с. — ISBN 978-5-397-00622-4.
 +
 
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Связность в графах]]

Текущая версия на 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), если он состоит из одной компоненты сильной связности.



См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Отношение_связности,_компоненты_связности&oldid=85378»