Маршруты, связные компоненты и расстояния в графе

Пусть – неориентированный граф. Маршрутомв называется чередующаяся последовательность вершин и ребер , такая, что ребра инцидентны вершинам . Вершина называется началом маршрута, а — концом. Одни и те же ребро и вершина могут встречаться в маршруте несколько раз. Будем называть маршрут цепью, если все его ребра различны. Цепь называется простой цепью, если все ее вершины, кроме, может быть, и , различны. (В ряде руководств по теории графов принята другая терминология: то, что мы называем маршрутом, называется цепью, то, что мы называем цепью, — простой цепью и то, что мы называем простой цепью, - элементарной цепью). Число n называется длиной цепи. Цепь (простая цепь) называется циклом (соответственно простым циклом), если = . Ниже, указывая маршрут в графе, будем обозначать его вершины и ребра так, как они в этом графе обозначены, не придерживаясь обозначений .

последовательность определяет маршрут с начало и концом , являющийся цепью, но не простой цепью. Маршрут цепью не является.

2. Как правило, маршрут в графе однозначно определяется последовательностью ребер, например, если любые два соседних ребра маршрута имеют только одну общую инцидентную вершину; вершина первого ребра, не инцидентная второму, является началом маршрута, а вершина последнего ребра, не инцидентная предпоследнему, - концом. Пользуясь этим замечанием, рассмотрим маршруты в следующем графе:

- цепь, не являющаяся простой цепью;

– простая цепь;

– цикл, не являющийся простым циклом;

– простой цикл.

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

Рассмотрим бинарное отношение R на множестве вершин графа: , если и — связанные вершины. Читателю предоставляется проверить, что это отношение является отношением эквивалентности. Следовательно, возникает разбиение множества вершин графа на классы эквивалентности: две вершины относятся к одному классу эквивалентности, если они являются связанными. Далее, рассмотрим один из классов эквивалентности вместе с множеством всех ребер, инцидентных вершинам из этого класса. Мы получим подграф данного графа, называемый компонентой связности. Граф, состоящий из одной компоненты связности, называется связным. (Можно сказать проще: граф связен, если любые две его вершины являются связанными).

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

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

Легко проверить, что обладает всеми свойствами расстояния (или метрики), определяемой на произвольном множестве, а именно:

1) тогда и только тогда, когда ;

2) ;

3) (неравенство треугольника).

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

С расстоянием между вершинами связаны понятия радиуса, диаметра и центра графа. Дадим нужные определения.

Максимальное расстояние между двумя вершинами графа G называется диаметром графа и обозначается . Кратчайшие простые цепи, связывающие вершины с максимальным расстоянием между ними, называются диаметральными цепями.

Максимальным удалением от вершины называется величина , равная максимальному расстоянию от до других вершин графа.

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

Пример.

Проверьте, что в следующем графе:

1) ;

2) ;

3) ;

4) , центры: , .