Определение связных и несвязных графов
Граф G (V, E) называется связным, если для любой пары различных вершин этого графа существует цепь, соединяющая эти вершины. Так как из существования цепи, соединяющей две вершины графа, следует существование простой цепи, соединяющей эти вершины (см. следствие 2 к упражнению 1 из пункта 1.10), то граф является связным, если любую пару его вершин соединяет по крайней мере одна простая цепь. Если для графа G (V, E) можно указать пару различных вершин, которые не соединяются цепью (простой цепью), то граф называется несвязным. Например, на рис. 1, 3, 6, 7а, 16, 8а, 9−12, 16- 18, 19а-19г, 20−23, 25 представлены связные графы, а на рис. 4 — несвязный граф.
Теорема 4. Граф G (V, Е) является несвязным тогда и только тогда, когда множество его вершин V можно разбить на два не пустых подмножества V/ и У2 так, чтобы любое ребро графа соединяло вершины из одного подмножества.
Доказательство. Пусть G (V, E) — несвязный граф. Зафиксируем некоторую вершину А графа и обозначим через Vi множество, состоящее из вершины А и всех тех вершин из V, которые соединены цепями с вершиной А. Множество V/ не пусто (оно содержит, по крайней мере, вершину А) и не совпадает со множеством V (в противном случае граф G (V, Е) — связный, так как между его любыми двумя различными вершинами существует цепь, проходящая через А). Рассмотрим дополнение V2=V-Vi. Множество V2 не пусто. Ясно, что никакое ребро графа G (V, E) не соединяет ни одну вершину из V/ ни с одной вершиной из V2. Поэтому построенные множества V/ и V2 образуют искомое разбиение множества V.
Обратно, пусть существует разбиение V = V/ U V2t удовлетворяющее условию теоремы. Докажем, что G (V, E) — несвязный граф. Рассмотрим произвольную пару вершин из разных подмножеств AG V/, Be V2, и докажем, что не существует цепи, соединяющей эти вершины. Действительно, если такая цепь существует, то она включает ребро, граничные точки которого принадлежат разным подмножествам, что противоречит условию. Теорема доказана.
