§ 4. Маршруты, связные компоненты и расстояния в графе
Пусть – неориентированный граф. Маршрутом в называется чередующаяся последовательность вершин и ребер , такая, что ребра инцидентны вершинам . Вершина называется началом маршрута, а — концом. Одни и те же ребро и вершина могут встречаться в маршруте несколько раз. Будем называть маршрут цепью, если все его ребра различны. Цепь называется простой цепью, если все ее вершины, кроме, может быть, и , различны. (В ряде руководств по теории графов принята другая терминология: то, что мы называем маршрутом, называется цепью, то, что мы называем цепью, — простой цепью и то, что мы называем простой цепью, - элементарной цепью). Число n называется длиной цепи. Цепь (простая цепь) называется циклом (соответственно простым циклом), если = . Ниже, указывая маршрут в графе, будем обозначать его вершины и ребра так, как они в этом графе обозначены, не придерживаясь обозначений .
П римеры. 1. В следующем графе
последовательность определяет маршрут с начало и концом , являющийся цепью, но не простой цепью. Маршрут цепью не является.
2. Как правило, маршрут в графе однозначно определяется последовательностью ребер, например, если любые два соседних ребра маршрута имеют только одну общую инцидентную вершину; вершина первого ребра, не инцидентная второму, является началом маршрута, а вершина последнего ребра, не инцидентная предпоследнему, - концом. Пользуясь этим замечанием, рассмотрим маршруты в следующем графе:
– маршрут, не являющийся цепью, с
началом и концом ;
- цепь, не являющаяся простой цепью;
– простая цепь;
– цикл, не являющийся простым циклом;
– простой цикл.
Вершины и называются связанными, если существует маршрут в графе с началом в и концом в . Легко видеть, что в этом случае существует и простая цепь с началом в и концом : в самом деле, если какая-нибудь вершина встречается несколько раз в последовательности, задающей маршрут, то, выбросив из последовательности все вершины и ребра между первым и последним появлением , мы получим маршрут, в котором встречается только один раз; повторив нужное число раз эту процедуру, получим искомую простую цепь.
Рассмотрим бинарное отношение R на множестве вершин графа: , если и — связанные вершины. Читателю предоставляется проверить, что это отношение является отношением эквивалентности. Следовательно, возникает разбиение множества вершин графа на классы эквивалентности: две вершины относятся к одному классу эквивалентности, если они являются связанными. Далее, рассмотрим один из классов эквивалентности вместе с множеством всех ребер, инцидентных вершинам из этого класса. Мы получим подграф данного графа, называемый компонентой связности. Граф, состоящий из одной компоненты связности, называется связным. (Можно сказать проще: граф связен, если любые две его вершины являются связанными).
П ример графа с двумя компонентами связности:
В графе можно удалять рёбра и вершины. Если удаляется ребро, то все вершины сохраняются, если же удаляется вершина, то удаляются все инцидентные ей рёбра. Вершина, при удалении которой число компонент связности увеличивается, называется точкой сочленения.
Р ебро с таким свойством называется мостом.
В изображенном графе G точками сочленения являются вершины Действительно, при удалении вершины связный граф G превращается в две компоненты,
так как удаляются рёбра , , . Аналогично при удалении получается вершина и связный граф.
При удалении получим
Мостами являются рёбра и .
Рассмотрим связный граф. Для любых двух его вершин существует связывающий их маршрут, который можно считать простой цепью. Эта простая цепь не единственна. Минимальная длина простой цепи, связывающей две вершины и связного графа, называется расстоянием между вершинами и обозначается .
Легко проверить, что обладает всеми свойствами расстояния (или метрики), определяемой на произвольном множестве, а именно:
тогда и только тогда, когда ;
;
(неравенство треугольника).
Для проверки последнего свойства положим , и рассмотрим простые цепи и , на которых достигаются и соответственно. Маршрут , очевидно, связывает с . Ясно, что не больше, чем число ребер в этом маршруте, то есть чем .
С расстоянием между вершинами связаны понятия радиуса, диаметра и центра графа. Дадим нужные определения.
Максимальное расстояние между двумя вершинами графа G называется диаметром графа и обозначается .
Максимальным удалением от вершины называется величина , равная максимальному расстоянию от до других вершин графа.
Вершина, максимальное удаление от которой минимально, называется центром графа, а значение максимального удаления от центра называется радиусом графа и обозначается . Отметим, что центр не единственен. Так, в полном графе ( в котором любые две вершины соединены единственным ребром) центром является любая вершина, а радиус и диаметр равны единице.
Пример.
Проверьте, что в следующем графе:
;
;
;
, центры: , .
О пределение максимального удаления и центра графа имеет важное практическое значение при размещении станций скорой помощи, отделений милиции, пожарных частей и других аварийных служб и пунктов обслуживания.