Отношение связности, компоненты связности — различия между версиями
Grechko (обсуждение | вклад) |
Grechko (обсуждение | вклад) |
||
| Строка 2: | Строка 2: | ||
|definition= | |definition= | ||
'''Компоненты связности''' неориентированного графа <math>G=(V, E)</math> — такие множества <math>C_i</math> что <math>C_i \subset V</math> и между любыми вершинами из одного множества существует путь, а между любыми вершинами из разных множеств не существует пути}} | '''Компоненты связности''' неориентированного графа <math>G=(V, E)</math> — такие множества <math>C_i</math> что <math>C_i \subset V</math> и между любыми вершинами из одного множества существует путь, а между любыми вершинами из разных множеств не существует пути}} | ||
| + | {{Теорема | ||
| + | |statement= | ||
| + | Для неориентированного графа <math>G=(V, E)</math> cемейство множеств <math>C_i</math> удовлетворяющих определению единственно и образует разбиение множества <math>V</math> | ||
| + | |proof= | ||
| + | Докажем что отношение существования пути, заданное на множестве вершин графа, разбивает множество <math>V</math> на '''классы эквивалентности''' <br> | ||
| + | '''Рефлексивность''': <math>\forall a \in V a \rightsquigarrow a</math> (Очевидно) <br> | ||
| + | '''Коммутативность''': <math>a\rightsquigarrow b \Rightarrow b\rightsquigarrow a</math> (В силу неориентированности графа) | ||
| + | '''Транзитивность''': <math>a\rightsquigarrow b \and b\rightsquigarrow c \Rightarrow a\rightsquigarrow c</math> (Очевидно) | ||
| + | }} | ||
Версия 06:21, 30 сентября 2010
| Определение: |
| Компоненты связности неориентированного графа — такие множества что и между любыми вершинами из одного множества существует путь, а между любыми вершинами из разных множеств не существует пути |
| Теорема: |
Для неориентированного графа cемейство множеств удовлетворяющих определению единственно и образует разбиение множества |
| Доказательство: |
|
Докажем что отношение существования пути, заданное на множестве вершин графа, разбивает множество на классы эквивалентности |
