Расстояние (теория графов)

• Расстояние между вершинами графа определяется как количество ребер на кратчайшем пути, соединяющем их. 
• Между двумя вершинами может быть более одного кратчайшего пути. 
• В случае ориентированного графа расстояние определяется как длина кратчайшего направленного пути. 
• Метрическое пространство графа определяется над набором точек в терминах расстояний на графе. 
• Множество вершин и функция расстояния образуют метрическое пространство, если граф связен. 
• Эксцентриситет вершины – это наибольшее расстояние между вершиной и любой другой вершиной. 
• Радиус графа – это минимальный эксцентриситет любой вершины. 
• Диаметр графа – это максимальный эксцентриситет любой вершины графа. 
• Геодезический граф – это граф, для которого каждая пара вершин имеет уникальный кратчайший путь. 
• Взвешенное расстояние по кратчайшему пути обобщает геодезическое расстояние для взвешенных графиков.