Пути, циклы, связность

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

Цикл ­– путь, у которого .

 

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

Шарнир (точка сочленения) в графе – вершина, при удалении которой увеличивается число компонент связности.

Перешеек – ребро, при удалении которого увеличивается число компонент связности.

 

Теорема о перешейках.Ребро является перешейком тогда и только тогда, когда через него не проходит ни один цикл.

 

В ориентированном графе можно определить два типа путей.

Ориентированный путь – это, как и в неориентированном случае, последовательность вершин , в которой каждая (упорядоченная) пара , , является ребром (и все эти ребра различны).

Неориентированный путь – последовательность вида , где , а – ребра графа, причем или для каждого .

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

Расстояния и метрические характеристики

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

Эксцентриситет вершины – расстояние от нее до самой удаленной вершины:

.

Диаметр графа – максимальное расстояние между вершинами, то есть наибольший эксцентриситет:

.

Радиус графа – наименьший эксцентриситет:

.

Центральная вершина – вершина, эксцентриситет которой равен радиусу графа.

Центр – множество всех центральных вершин.

 

Диаметр и радиус графа связаны соотношениями:

 

.