Тема 15.3. Расстояния. Диаметр, радиус и центр графа. Протяжённости.

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

Штрихи в обозначении используются, потому что не обязательно дуги под одинаковыми индексами будут совпадать.

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

Определение: Минимальная длина простой цепи с началом в вершине и концом в вершине называется расстоянием между этими вершинами. Обозначается: .

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

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

2) .

Также для расстояния выполняется неравенство треугольника: для любых трёх вершин выполняется неравенство: .

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

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

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

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

Определение: Вершина называется центром графа , если максимальное удаление от неё до остальных вершин графа принимает минимальное значение: .

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

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

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

Определение: Протяжённостью называется максимальная из длин связывающих эти вершины простых цепей.

Дата добавления: 2015-10-28