Маршруты и связность

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

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

Маршрут называется цепью, если все его ребра различны и простой цепью, если вершины различны.

Замкнутая цепь называется циклом.

Замкнутый маршрут (цепь) называется простым циклом, если все его вершины различны и n>=3.

Граф называется связным, если любая пара его вершин соединена простой цепью.

V5

V4

Ex:

Рис. 6

На рис.6 дан помеченный граф, укажем некоторые

маршруты в этом графе:

V1

V3

V2

1) V1,V2,V3,V4,V5 - этот маршрут не является цепью, т.к

чтобы из вершины V3 достигнуть V4, нужно или пройти через вершину V2 или через вершину V5. И в том и в другом случае мы повторяем какое-либо ребро графа, а маршрут называется цепью, если все его ребра различны.

2) Если указать маршрут V1,V2,V5,V4,V2,V3 - то это цепь, т.к. мы ни разу не повторили ребро, но не простая цепь, т.к два раза повторили вершину V2.

3) V1,V2,V5,V4 - это простая цепь, т.к. при движении по данному маршруту не повторяются ни ребра, ни вершины.

4) V2,V4,V5,V2 - это цикл, т.к. цепь замкнута и простой цикл, т.к. количество ребер n=3.

Длина маршрута V0,V1,V2,..,Vn=n, т.е. количеству ребер в нем, причем каждое ребро считается столько раз, сколько оно встречается в данном маршруте.

Для рис.6 длина маршрута равна:

1) n=5;

2) n=5;

3) n=3;

4) n=3.

Расстоянием d (u,v) между двумя вершинами u и v графа G называется длина кратчайшей простой цепи, соединяющей их.

Если u и v не соединены, то полагают d (u,v)=∞, т.е.по существу расстояние d (u,v) и длина маршрута суть одно и тоже, например, из рис.6 d(V1,V4)=2.

Именно с нахождением маршрута и его длины связано большинство задач для графов, решаемых с помощью ПК.

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

Существуют задачи отыскания маршрутов, проходящих через каждую вершину и имеющих минимальную длину или проходящую через каждую вершину только один раз (пути Эйлера) и т.д.