В поле математический в теории графов, расстояние между двумя вершинами в графе - это количество ребер в кратчайшем пути (также называемом геодезическим графом ) соединяя их. Это также известно как геодезическое расстояние . Обратите внимание, что между двумя вершинами может быть несколько кратчайших путей. Если нет пути, соединяющего две вершины, т.е. если они принадлежат разным компонентам связности, то условно расстояние определяется как бесконечное.
В случае ориентированного графа расстояние между двумя вершинами и определяется как длина кратчайшего направленного пути от до , состоящих из дуг, при условии, что существует хотя бы один такой путь. Обратите внимание, что, в отличие от случая неориентированных графов, не обязательно совпадает с , и может случиться так, что один определен, а другой нет.
A метрическое пространство, определенное над набором точки в терминах расстояний в графе, определенном по набору, называются метрикой графика . Множество вершин (неориентированного графа) и функция расстояния образуют метрическое пространство, если и только если граф связан.
эксцентриситетвершины - наибольшее расстояние между и любая другая вершина; в символах: . Можно представить себе, как далеко узел находится от наиболее удаленного от него узла на графике.
radiusграфа - это минимальный эксцентриситет любой вершины или, выражаясь символами, .
диаметрграфика - это максимальный эксцентриситет любой вершины графа. То есть - наибольшее расстояние между любой парой вершин или, альтернативно, . Чтобы найти диаметр графа, сначала найдите кратчайший путь между каждой парой вершин. Наибольшая длина любого из этих путей - это диаметр графа.
A центральная вершина в графике с радиусом - это вершина, эксцентриситет которой равен , т.е. есть вершина, которая достигает радиуса, или, что то же самое, вершина такая, что .
A периферийная вершина на графике диаметром - это вершина, которая находится на расстоянии от некоторая другая вершина, то есть вершина, которая достигает диаметра. Формально является периферийным, если .
A псевдопериферийная вершина имеет свойство, которое для любой вершины , если находится как можно дальше от , тогда так же далеко от насколько возможно. Формально вершина u является псевдопериферийной, если для каждой вершины v с содержит .
разбиение вершин графа на подмножества по их расстояниям из заданной начальной вершины называется структурой уровня графа.
Граф, в котором для каждой пары вершин существует уникальный кратчайший путь, соединяющий их, называется геодезическим графом. Например, все деревья являются геодезическими.
Часто периферийным алгоритмам разреженной матрицы требуется начальная вершина с высокий эксцентриситет. Периферийная вершина была бы идеальной, но ее часто трудно вычислить. В большинстве случаев можно использовать псевдопериферическую вершину. Псевдопериферийная вершина может быть легко найдена с помощью следующего алгоритма: