1.6. Расстояния в графе
Пусть - граф (или псевдограф). Расстоянием между вершинами называется минимальная длина пути между ними, при этом , , если не пути.
Расстояние в графе удовлетворяют аксиомам метрики
1) ,
2) (в неориентированном графе)
3)
4) в связном неориентированном графе.
Пусть связный граф (или псевдограф).
Диаметром графа G называется величина .
Пусть .
Максимальным удалением (эксцентриситетом) в графе G от вершины называется величина .
Радиусом Графа G называется величина
Центром графа G Называется любая вершина такая, что .
< Предыдущая | Следующая > |
---|