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. Если граф связен, то граф ), получающийся после удаления циклического ребра , тоже связен. Доказательство этой теоремы оставим в качестве упражнения.