Расстояния в графе
Пусть - граф (или псевдограф). Расстоянием между вершинами называется минимальная длина пути между ними, при этом , , если не пути.
Расстояние в графе удовлетворяют аксиомам метрики
1) ,
2) (в неориентированном графе)
3)
4) в связном неориентированном графе.
Пусть связный граф (или псевдограф).
Диаметром графа G называется величина .
Пусть .
Максимальным удалением (эксцентриситетом) в графе G от вершины называется величина .
Радиусом графа G называется величина
Центром графа G называется любая вершина такая, что .
Дата добавления: 2015-09-27 | Просмотры: 482 | Нарушение авторских прав
|