Путь, цепь, связность

Определение. Путем в неориентированном графе называется любая последовательность вида: , которая обозначается , все и пары .

Путь, где не повторяются ребра, называется цепью. Путь, где не повторяются вершины называется простой цепью. Длиной пути называется число ребер, входящих в путь.

Путь замкнут, если . Замкнутая цепь называется циклом, замкнутая простая цепь – простым циклом.

Лемма о существовании простой цепи. Пусть путь из в в неориентированном графе . Тогда можно выбрать подпуть , который будет простой цепью.

Доказательство. Если в вершины не повторяются, то он и есть простая цепь. Если в этом пути существует повторяющаяся вершина , то он имеет вид:

, где последовательности вершин и ребер.

Рассмотрим подпуть , вершина в этом пути уже не повторяется. Если в нет повторяющихся вершин, то он и есть простая цепь и теорема доказана. В противном случае повторим процедуру удаления повторяющейся вершины, так как число ребер и вершин конечно, то процесс завершится и мы получим простую цепь.

Говорят, вершина связана с вершиной в неориентированном графе, если существует путь .

Определение. Неориентированный граф называется связным, если любые две его вершины связаны.

Связанность вершин задает некоторое отношение на множестве вершин. Пара тогда и только тогда, когда существует . Будем считать, что (длина пути в этом случае равна 0). Если , то . Если и , тогда, очевидно , таким образом, отношение рефлексивно, симметрично и транзитивно, следовательно, оно является отношением эквивалентности.

Отношение эквивалентности позволяет разбить множество вершин на классы эквивалентности:

, где .

Две вершины связаны тогда и только тогда, когда они принадлежат одному классу эквивалентности.

Определение. Связной компонентой графа называется подграф , где класс эквивалентности на множестве вершин, , причем в входят все ребра из Е, инцидентные вершинам множества .