Определение. Путем в неориентированном графе называется любая последовательность вида: , которая обозначается , все и пары .
Путь, где не повторяются ребра, называется цепью. Путь, где не повторяются вершины называется простой цепью. Длиной пути называется число ребер, входящих в путь.
Путь замкнут, если . Замкнутая цепь называется циклом, замкнутая простая цепь – простым циклом.
Лемма о существовании простой цепи. Пусть путь из в в неориентированном графе . Тогда можно выбрать подпуть , который будет простой цепью.
Доказательство. Если в вершины не повторяются, то он и есть простая цепь. Если в этом пути существует повторяющаяся вершина , то он имеет вид:
, где последовательности вершин и ребер.
Рассмотрим подпуть , вершина в этом пути уже не повторяется. Если в нет повторяющихся вершин, то он и есть простая цепь и теорема доказана. В противном случае повторим процедуру удаления повторяющейся вершины, так как число ребер и вершин конечно, то процесс завершится и мы получим простую цепь.
Говорят, вершина связана с вершиной в неориентированном графе, если существует путь .
Определение. Неориентированный граф называется связным, если любые две его вершины связаны.
Связанность вершин задает некоторое отношение на множестве вершин. Пара тогда и только тогда, когда существует . Будем считать, что (длина пути в этом случае равна 0). Если , то . Если и , тогда, очевидно , таким образом, отношение рефлексивно, симметрично и транзитивно, следовательно, оно является отношением эквивалентности.
Отношение эквивалентности позволяет разбить множество вершин на классы эквивалентности:
, где .
Две вершины связаны тогда и только тогда, когда они принадлежат одному классу эквивалентности.
Определение. Связной компонентой графа называется подграф , где класс эквивалентности на множестве вершин, , причем в входят все ребра из Е, инцидентные вершинам множества .
Каждый неориентированный граф единственным образом представляется в виде объединения своих связных компонент.
На рис. 15 показан граф, состоящий из четырех связных компонент.
Рис. 15 |