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