Определение. Пусть 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)...

Определение. Неориентированным графом (просто графом или неографом) называется пара множеств, первое из которых представляет собой конечное множество V, называемое множе­ством вершин, второе – множество Е двухэлементных подмножеств множества V, называемое множеством неориентированных рёбер (или просто рёбер). Определение. Элемент множества Е называется неориентированным ребром (или просто ребром). Неориентированный граф обозначается G(V, E), а для записи нескольких различных графов рекомендуется...