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