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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Связность)
(Слабая связность)
Строка 23: Строка 23:
 
{{Определение
 
{{Определение
 
|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> }}
+
Пусть <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> }}
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=

Версия 09:36, 18 января 2011

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

Связность

Определение:
Компоненты связности неориентированного графа [math]G=(V, E)[/math] — такие множества [math]C_i[/math], что [math]C_i \subset V[/math] и между любыми вершинами из одного множества существует путь, а между любыми вершинами из разных множеств - нет
Теорема:
Для неориентированного графа [math]G=(V, E)[/math] cемейство множеств [math]C_i[/math] удовлетворяющих определению единственно и образует разбиение множества [math]V[/math]
Доказательство:
[math]\triangleright[/math]

Докажем что отношение существования пути, заданное на множестве вершин графа, разбивает множество [math]V[/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]\triangleleft[/math]
Определение:
Граф [math]G=(V, E)[/math] называется связным, если он состоит из одной компоненты связности. В противном случае граф называется несвязным


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

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

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

Определение:
Пусть [math]G = (V, E)[/math] — ориентированный граф. Рассмотрим граф [math]G' = (V, E')[/math], составленный из вершин графа [math]G[/math], в котором ребро [math](x, y)[/math] существует тогда и только тогда, когда [math](x, y) \in E \lor (y, x) \in E[/math] Скажем что между вершинами [math]v \in G[/math] и [math]u \in G[/math] существет неориентированный путь, если [math]v[/math] и [math]u[/math] связаны путем в [math]G'[/math]


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


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


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

Пусть [math]G=(V, E) [/math] — ориентированный граф. Введем отношение на вершинах графа: [math]R(v, u) = v \rightsquigarrow u \land u \rightsquigarrow v[/math]. Очевидно, [math]R[/math] рефлексивно, коммутативно, транзитивно.

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


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