Метрические характеристики графов

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

Функция обладает следующими свойствами:

1. , причем тогда и только тогда, когда ;

2. ;

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

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

Расстояние от данной вершины до наиболее удаленной от нее вершины называется эксцентриситетом вершины и обозначается через . Таким образом,

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

Наименьший диаметр имеет полный граф - его диаметр равен 1. Среди связных графов с вершинами наибольший диаметр, равный , имеет цепь .

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

Для графа, изображенного на рис. 2.3, эксцентриситеты вершин приведены в следующей таблице:

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

Рис. 2.3.

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

Для ориентированного графа можно определить два типа маршрутов. Неориентированный маршрут (или просто маршрут) - это чередующаяся последовательность вершин и ребер графа, такая, что для каждого выполняется одно из двух: или . Маршрут называется ориентированным (или ормаршрутом), если для каждого . Таким образом, при движении вдоль маршрута в орграфе ребра могут проходиться как в направлении ориентации, так и в обратном направлении, а при движении вдоль ормаршрута - только в направлении ориентации. Это различие очевидным образом распространяется на пути и циклы, так что в орграфе можно рассматривать пути и орпути, циклы и орциклы. Будем говорить, что маршрут соединяет вершины и , а ормаршрут ведет из в .

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

Рис. 2.4.