1.4. Связность и компоненты графа
Важным понятием в теории графов является связность. Две вершины 
называются связанными в графе G, если в нем существует путь 
Вершина связана сама с собой.
Граф G называется связным, если в нем существует путь между каждой парой вершин. Например, граф, представленный на рис. 1.6, связный.
Рассмотрим несвязный граф 
. Тогда множество вершин V графа G можно разбить u на такие подмножества 
что вершинно-порожденные подграфы 
, связны, и никакая вершина подмножества 
не связана ни с какой вершиной подмножества 
Рис. 1.7. Граф С с компонентами 
Подграфы 
, называются компонентами графа G. Легко видеть, что компонентой графа G является максимально связный подграф графа G, т. е. компонента графа G не является собственным подграфом любого другого связного подграфа графа 
Например, граф G на рис. 1.7 не связен. Его четыре компоненты 
имеют множества вершин 
соответственно.
Отметим, что изолированную вершину также следует рассматривать как компоненту, поскольку по определению вершина связана сама с собой. Кроме того, следует отметить, что если граф 
связен, то он имеет только одну компоненту, которая является графом G. Теперь рассмотрим некоторые свойства связных графов.
Теорема 1.3. В связном графе любые два пути максимальной длины имеют обшую вершину.
Доказательство. Рассмотрим произвольные пути максимальной длины 
в связном графе G. Обозначим через 
последовательность вершин 
а через 
— последовательность 
Предположим, что 
не имеют общей вершины. Поскольку граф G связен, то для некоторых i, 
существует 
-путь 
такой, что все вершины 
кроме 
- и 
отличны от вершин 
Пути 
могут быть такими, как показано на рис. 1.8. Пусть — длина 
-пути 
— длина 
— 
-пути 
— длина 
— длина 
- пути 
— длина пути 
. Пути 
также представлены на рис. 1.8.
Рис. 1.8. Пути 
.
Отметим, что 
максимальная длина пути в графе G, а 
Не нарушая общности, предположим, что и поэтому 
Легко видеть, что пути 
вместе составляют путь 
длина которого равна 
так как 
Это противоречит тому, что 
является максимальной длиной пути в графе 
Следующая теорема будет часто использоваться в обсуждениях гл. 2. В дальнейшем будем заменять 
на 
всякий раз, когда ясно, что мы ссылаемся на множество, а не на его элемент.
Теорема 1.4. Если граф 
связен, то граф 
), получающийся после удаления циклического ребра 
, тоже связен. Доказательство этой теоремы оставим в качестве упражнения.
