Пусть - связный неориентированный граф. Так как любые две вершины графа и связаны, то существуют простые цепи с концами и . Таких цепей может быть несколько. Их длины являются неотрицательными целыми числами. Следовательно, между вершинами и должны существовать простые цепи наименьшей длины. Длина цепи наименьшей длины, связывающей вершины и , обозначается символом и называется расстоянием между вершинами и . По определению .
Нетрудно убедиться, что введенное таким образом понятие расстояния, удовлетворяет аксиомам метрики:
Пусть - связный неориентированный граф. Так как любые две вершины графа и связаны, то существуют простые цепи с концами и . Таких цепей может быть несколько. Их длины являются неотрицательными целыми числами. Следовательно, между вершинами и должны существовать простые цепи наименьшей длины. Длина цепи наименьшей длины, связывающей вершины и , обозначается символом и называется расстоянием между вершинами и . По определению .
Нетрудно убедиться, что введенное таким образом понятие расстояния, удовлетворяет аксиомам метрики:
1. ;
2. тогда и только тогда, когда ;
3. ;
4. справедливо неравенство треугольника: