Редактирование: Отношение связности, компоненты связности

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Две вершины <tex>u</tex> и <tex>v</tex> называются '''связаными''' ''(англ. adjacent)'', если в графе <tex>G</tex> существует [[Основные определения теории графов|путь]] из <tex>u</tex> в <tex>v</tex> (обозначение: <tex>u \rightsquigarrow 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=
Связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]''' ''(англ. equivalence relation)''.
+
Связность {{---}} '''[[Отношение_эквивалентности|отношение эквивалентности]]''' ''(equivalence relation)''.
 
|proof=
 
|proof=
 
'''[[Рефлексивное_отношение|Рефлексивность]]''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно).
 
'''[[Рефлексивное_отношение|Рефлексивность]]''': <tex>\forall a \in V a \rightsquigarrow a</tex> (очевидно).
Строка 19: Строка 19:
 
|id = def2
 
|id = def2
 
|definition=
 
|definition=
'''Компонентой связности''' ''(англ. connected component)'' называется класс эквивалентности относительно связности.}}
+
'''Компонентой связности''' ''(connected component)'' называется класс эквивалентности относительно связности.}}
  
 
{{Определение
 
{{Определение
 
|id = connected_graph
 
|id = connected_graph
 
|definition=
 
|definition=
Граф <tex>G=(V, E)</tex> называется '''связным''' ''(англ. connectivity graph)'', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}}
+
Граф <tex>G=(V, E)</tex> называется '''связным''' ''(connectivity graph)'', если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''.}}
  
 
== Случай ориентированного графа ==
 
== Случай ориентированного графа ==
Строка 31: Строка 31:
 
<wikitex>{{Определение
 
<wikitex>{{Определение
 
|definition=
 
|definition=
Отношение $R(v, u)$ называется отношением '''слабой связности''' ''(англ. weak connectivity)'', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.
+
Отношение $R(v, u)$ называется отношением '''слабой связности''' ''(weak connectivity)'', если вершины $u$ и $v$ связаны в неориентированном графе $G'$, полученном из графа $G$ удалением ориентации с рёбер.
 
}}
 
}}
  
Строка 48: Строка 48:
 
|id=sc_def
 
|id=sc_def
 
|definition=
 
|definition=
Отношение <tex>R(v, u) = v \rightsquigarrow u \land  u \rightsquigarrow v</tex> на вершинах графа называется отношением '''сильной связности''' ''(англ. strong connectivity)''.
+
Отношение <tex>R(v, u) = v \rightsquigarrow u \land  u \rightsquigarrow v</tex> на вершинах графа называется отношением '''сильной связности''' ''(strong connectivity)''.
 
}}
 
}}
  
Строка 61: Строка 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|Пример ориентированного графа с тремя компонентами сильной связности.]]
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
[[Основные_определения_теории_графов|Ориентированный граф]] <tex>G = (V, E)</tex> называется '''сильно связным''' ''(англ. strongly connected)'', если он состоит из одной компоненты сильной связности.}}
+
[[Основные_определения_теории_графов|Ориентированный граф]] <tex>G = (V, E)</tex> называется '''сильно связным''' ''(strongly connected)'', если он состоит из одной компоненты сильной связности.}}
  
 
<br clear="all" />
 
<br clear="all" />
Строка 71: Строка 71:
 
==См. также==
 
==См. также==
  
*[[Отношение рёберной двусвязности]]
+
*[[Отношение_реберной_двусвязности|Отношение реберной двусвязности]]
*[[Отношение вершинной двусвязности]]
+
*[[Отношение_вершинной_двусвязности|Отношение вершинной двусвязности]]
  
 
==Источники информации==
 
==Источники информации==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: