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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
== Компоненты связности ==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Строка 11: Строка 12:
 
'''Транзитивность''': <math>a\rightsquigarrow b \and b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</math> (Очевидно)
 
'''Транзитивность''': <math>a\rightsquigarrow b \and b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</math> (Очевидно)
 
}}
 
}}
 +
== Связные графы ==
 +
{{Определение
 +
|definition=
 +
Граф <math>G=(V, E)</math> называется '''связным''' если он состоит из одной компоненты связности. В противном случае граф называется '''несвязным'''}}

Версия 07:17, 30 сентября 2010

Компоненты связности

Определение:
Компоненты связности неориентированного графа [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 \and b\rightsquigarrow c \Rightarrow a\rightsquigarrow c[/math] (Очевидно)
[math]\triangleleft[/math]

Связные графы

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