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

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

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

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

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

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

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

2) .

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

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

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

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

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

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

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

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

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

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