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

Глава II. Теория графов

Основные определения

Говоря нестрого, граф— это множество точек (вершин) и соединяющих их криволинейных отрезков (ребер). Типичный пример графа — схема каких-либо транспортных путей, например, автомобильных дорог. Пункты назначения — это вершины графа, а соединяющие их дороги — ребра. Возникают задачи поиска пути в графе, обладающего тем или иным свойством. Например, можно требовать, чтобы каждое ребро проходилось не более одного раза; можно — чтобы каждая вершина. Можно каждому ребру сопоставить положительное число (длина дороги), и заниматься поисками кратчайшего пути от одного пункта до другого.

В ряде случаев ребру графа придается направление, то есть одна из двух точек, которые это ребро соединят, считается начальной, а другая – конечной. Так, например, естественно поступить, если ребро изображает дорогу с односторонним движением. Направление ребра изображается стрелкой. Граф с направленными ребрами называется ориентированным. Если направления ребер не фиксируются, то граф называется неориентированным. Не исключено также, что одна пара вершин соединена несколькими ребрами (такие ребра называются кратными) или одно ребро соединяет вершину с самою собой (такое ребро называется петлей). Некоторые вершины могут вообще ни с какими другими вершинами не соединяться ребрами — такие вершины называются изолированными.

Рис. 1 Рис. 2

На рис.1 изображен неориентированный граф, вершины которого обозначены римскими цифрами, а ребра — арабскими. Ребра 3 и 4 являются кратными — они соединяют вершины II и III. Ребро 5 является петлей. Вершина IX — изолированная. Заметим, что ребра 2 и 1, 9 и 8 пересекаются на рисунке, но точки их пересечения не являются вершинами графа. (Вопрос о том, можно ли изобразить на плоскости граф так, чтобы его различные ребра не пересекались, будет рассмотрен в § 14). На рисунке 2 изображен ориентированный граф. Он также имеет кратные ребра (1 и 2), петлю (3), изолированную вершину (VI).

Дадим теперь точные определения.

Графом называется пара (V, Е), где V — множество вершин, Е — множество ребер. Мы будем рассматривать только конечные графы, то есть множества V и Е будем считать конечными. Если ребро е соединяет вершины v₁ и v₂, то будем говорить, что е инцидентновершинам v₁ и v₂, и наоборот, что каждая из вершин v₁, v₂ инцидентна ребру е. Иногда ребро е, соединяющее вершины v₁ и v₂, удобно обозначать парой (v₁, v₂), причем, если граф ориентирован, то пара (v₁, v₂) считается упорядоченной, вершина v₁ называется началом ребра, а v₂ — концом. Если же граф не ориентирован, то порядок элементов в паре (v₁, v₂), обозначающей ребро, не существенен.

Граф H называется частью графа G, если множество вершин H содержится во множестве вершин G, а множество ребер H — во множестве ребер G. Если при этом множество вершин H совпадет с множеством вершин G, то H называется суграфом или остовом графа G. Если H содержит все ребра графа G, соединяющие вершины, принадлежащие множеству вершин H, то H называется подграфом графа G.

Изоморфизм графов.

Пусть G(V, Е) и G’ = (V’, Е’) – два графа. Скажем, что эти два графа изоморфны, если существует пара биективных отображений j: V ®V’, y: Е®Е’ таких, что для любого ребра е = (v₁, v₂)ÎЕ y(е) = (j(v₁), j(v₂)). Иными словами, отображение y переводит ребро, соединяющее две вершины, в ребро, соединяющее образы этих вершин при отображении j.

Изоморфными могут быть на первый взгляд непохожие друг на друга графы.

Примеры. 1

Изоморфизм этих двух графов задается отображением вершин j: x_i®у_i, i =1,2,3,4; ребро (х_i, х_j) переводится отображением y в ребро (у_i,у_j). Заметим, что данные графы являются полными, то есть вместе с любыми двумя вершинами содержат единственное соединяющее их ребро. Полные графы с n вершинами обозначаются K_n. Ясно, что любые два полных графа с одинаковым количеством вершин изоморфны.

Изоморфизм этих двух графов зададим отображением вершин с помощью подстановки:

(вершина х_i переходит в вершину у_i расположенную под ней; ребро (х_i, х_k) переходит в соответствующее ребро (у_j, у_l), где х_i переходит в у_j, а х_k — в у_l). Как устроен этот изоморфизм ясно: семиугольник с вершинами х₁,…,х₇ переходит в ломаную, составленную из диагоналей семиугольника с вершинами у,…,у; наоборот — диагонали семиугольника слева переходят в стороны семиугольника справа.

Ясно, что у изоморфных графов должно быть одинаковое число вершин и ребер. Однако этого условия не достаточно для изоморфизма. Пусть, например, последовательность ребер образует цикл, то есть конец каждого предыдущего ребра является началом последующего и конец последнего ребра совпадает с началом первого; число ребер последовательности называется длиной цикла (точные определения см. в § 5). Очевидно, при изоморфизме цикл переходит в цикл той же длины. Значит, у изоморфных графов должно быть одинаковое число циклов определенной длины. Следующие два графа

неизоморфны, так как у одного из них два цикла длины 4, а у другого – один.

Степени вершин графа

В этом пункте граф будет предполагаться неориентированным.

Степенью вершины графа называется количество ребер, инцидентных вершине. Необходимо, однако, уточнить понятие степени в случае, когда среди ребер, инцидентных данной вершине, есть петля. Можно считать петлю за одно ребро, а можно — за два (подразумевая, что петля имеет «два входа» в вершину). В первом случае степень вершины будет обозначаться , во втором — .

Пример.

Для вершины данного графа , .

Теорема.Пусть граф имеет ребер и вершин . Тогда

.

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

Следствие.

Число вершин графа нечетной степени четно.

Уже эта простая теорема позволяет решить ряд интересных задач.

Пример. Утверждают, что в одной компании из 7 человек каждый знаком с тремя и только тремя другими. Возможна ли такая компания?

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

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

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

Примеры. 1. В следующем графе

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

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

– маршрут, не являющийся цепью, с

началом и концом ;

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

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

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

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

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

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

Пример графа с двумя компонентами связности:

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

Ребро с таким свойством называется мостом.

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

так как удаляются рёбра , , . Аналогично при удалении получается вершина и связный граф.

При удалении получим

Мостами являются рёбра и .

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

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

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

2) ;

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

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

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

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

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

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

Пример.

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

1) ;

2) ;

3) ;

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

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