211 читали · 2 года назад
Расстояние в неориентированном графе
Определение. Пусть G – связный неориентированный граф, включающий вершины u и v. Расстоянием d(u, v) между вершинами u и v называется длина самой короткой цепи, соединяющей эти вершины. По определению d(u, u) = 0. Заметим, что введенное таким образом понятие расстояния между вершинами удовлетворяет аксиомам метрики: 1) d(u, v) больше либо равно 0; 2) d(u, v) = 0 тогда и только тогда, когда u = v; 3) d(u, v) = d(v,u); 4) справедливо неравенство треугольника: d(u,w) меньше либо равно d(u,v) + d(v,w)...