Маршруты , пути, циклы

Маршрутом в неориентированном графе G называется последовательность вершин и ребер, таким образом, что некоторое ребро Хi=ViVi+1 (i=1,2,…,n).

Пример: В графе, изображенном на рис.3, v1x1v2x2v3x4v4x3v2 - маршрут, v2x2v3x4v4 – подмаршрут;

Маршрут можно восстановить и по такой записи x1x2x4x3 ;

если кратности ребер (дуг) равны 1, можно записать и так v1v2v3v4v2 .

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

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

Циклический маршрут называется циклом, если он является цепью, и простым циклом – если простой цепью.

Вершины v 1 и v 2 называются связанными вершинами, если существует маршрут М с началом v 1 и концом v 2 .

Граф G называется связным, если все его вершины связаны между собой.

Все связанные подграфы графа называются связанными компонентами графа.

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

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

Контур – путь, в котором v 0= v k. Контур называется циклом, если он является цепью, и простым циклом, когда это простая цепь.

Граф, не содержащий циклов, называется ациклическим.

Говорят, что вершина w ориентированного графа D (графа G) достижима из вершины v, если либо w = v, либо существует путь (маршрут) из v в w.

Граф (ориентированный граф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v и w. Число ребер маршрута (пути) называется его длиной.

Расстояния в графе

Пусть - граф (или псевдограф). Расстоянием между вершинаминазывается минимальная длина пути между ними, при этом,, если непути.

Расстояние в графе удовлетворяют аксиомам метрики:

1) ,

2) (не в ориентированном графе)

3)

4) в связном графе (не в ориентированном графе).

Пусть связный граф (или псевдограф).

Диаметром графа G называется величина

.

Пусть .

Максимальным удалением (эксцентриситетом) в графе G от вершины называется величина

Радиусом графа G называется величина

Центром графа G называется любая вершина такая, что.

Множество всех центральных вершин графа называется его центром.

Под длиной (или весом) любого подграфа взвешенного графа будем понимать сумму весов его ребер.

Эйлеров цикл – цикл, содержащий все ребра графа.

Эйлеров граф – граф, имеющий эйлеров цикл.

Эйлерова цепь – цепь, включающая все ребра G-графа, но имеющая различные начало и конец.

Утверждение 1: Для того чтобы связный граф G обладал эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.

Утверждение 2: Для того чтобы связный граф G обладал эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.

Гамильтонов цикл – простой цикл, проходящий через все вершины рассматриваемого графа.

Гамильтонова цепь – простая цепь, проходящая через все вершины графа, с началом и концом в разных вершинах.