1.7. Связность

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

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

Другое определение связности графа дается следующей теоремой.

Теорема 1.4. Граф связен тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества и так, что обе граничные точки каждого ребра находятся в одном и том же подмножестве.

Доказательство. Пусть несвязен. Выберем произвольную вершину и пусть множество состоит из вершины вместе со всеми вершинами, которые могут быть соединены с цепью. Так как несвязен, (оставляем читателю показать почему), поэтому дополнение непусто. Согласно методу построения множества ни одно ребро не соединяет вершину из ни с одной вершиной из откуда и получаем разбиение, указанное в формулировке теоремы.

Обратно, если такое разбиение существует, произвольно выбираем вершины и Цепь, соединяющая обязательно должна содержать, по крайней мере, одно ребро, имеющее граничные точки в обеих множествах и а так как такого ребра не существует, то граф несвязан. Доказательство закончено.

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

рефлексивно для любого оимметрично следует, что и транзитивно следует Таким образом, есть отношение эквивалентности. Оно разбивает множество V единственным образом на классы эквивалентности взаимно связанных вершин. Для графа, изображенного на рис. 1.1, такими классами эквивалентности являются Каждый класс эквивалентности вершин вместе с ребрами из инцидентными этим вершинам, образует связный подграф, называемый просто компонентой Легко видеть, что компонента графа является максимальным связным подграфом в том смысле, что граф не имеет связного собственного надграфа.

Упражнения

(см. скан)