Структуры и алгоритмы компьютерной обработки данных (стр. 12 )

У графа на рис. 3.2 имеется четыре области связности - , , , .

Рис. 3.2.

Вершина называется шарниром (или точкой сочленения), если при ее удалении число компонент связности увеличивается. У графа на рис. 3.2 имеется четыре шарнира - это вершины , , , .

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

Легко доказываются следующие свойства шарниров и перешейков:

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

Теорема 4. Ребро является перешейком в том и только том случае, если в графе нет простого цикла, содержащего это ребро.

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

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

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

, причем тогда и только тогда, когда ; ; (неравенство треугольника).

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

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

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

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

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

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

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

Рис. 3.3.

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

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