Определение. Пусть 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).
Определение. Пусть G – связный неориентированный граф со множеством вершин V, d(u, v) – расстояние между вершинами u и v. Эксцентриситетом (максимальным удалением) вершины u называется величина
Заметим, что в полном графе эксцентриситет каждой вершины равен единице, а в неориентированном графе, имеющем простые циклы длины n, эксцентриситет каждой вершины равен n\2.
Определение. Пусть G – неориентированный граф. Пусть MР − матрица, строки и столбцы которой обозначены вершинами графа. Элементы, находящиеся на пересечении строки u и столбца v матрицы MР, обозначаемые dij, равны расстоянию d(u,v) между вершинами u и v. Матрица MР называется матрицей расстояний графа G.
Свойства матрицы расстояний:
1) значения расстояний всегда неотрицательны, поэтому и элементы матрицы расстояний неотрицательны;
2) если неориентированный граф G является графом без петель, то элементы главной диагонали матрицы расстояний все нулевые;
3) матрица расстояний симметрична относительно главной диагонали;
4) выполняется неравенство треугольника: dik меньше либо равно dij + djk.
Для демонстрации примеров приведём несколько примеров графов G1 – G3.
Пример 1. Определим эксцентриситет для неориентированных графов G1– G3, показанных на рис. выше.
Для неориентированного графа G1 получаем:
d(a,b) = 1, d(a,c) = 1, d(a,d) = 2, d(a,e) = 2, d(a,f) = 3,
d(b,c) = 2, d(b,d) = 1, d(b,e) = 3, d(b,f) = 2,
d(c,d) = 1, d(c,e) = 1, d(c,f) = 2,
d(d,e) = 2, d(d,f) = 1,
d(e,f) = 3,
следовательно, e(a) = e(b) = e(e) = e(f) = 3, e(c) = e(d) = 2.
Для неориентированного графа G2 получаем:
d(a,b) = 4, d(a,c) = 1, d(a,d) = 2, d(a,e) = 3, d(a,f) = 3,
d(b,c) = 3, d(b,d) = 2, d(b,e) = 1, d(b,f) = 3,
d(c,d) = 1, d(c,e) = 2, d(c,f) = 2,
d(d,e) = 1, d(d,f) = 1,
d(e,f) = 2,
следовательно, e(a) = e(b) = 4, e(c) = e(e) = e(f) = 3, e(d) = 2.
Для неориентированного графа G3 получаем d(a,a) = 0, следовательно, e(a) = 0.
Пример 2. Запишем матрицы расстояний для неориентированных графов G1– G3, показанных на рис. выше.
Неориентированный граф G1 состоит из шести вершин, поэтому его матрица расстояний имеет размерность 6 на 6:
Неориентированный граф G2 также состоит из шести вершин, поэтому его матрица расстояний также имеет размерность 6 на 6:
Неориентированный граф G3 состоит из единственной вершины, поэтому его матрица расстояний имеет размерность 1 на 1, другими словами, имеет единственный элемент, равный нулю.
Определение. Пусть G – связный неориентированный граф, e(u) – эксцентриситет (максимальное удаление) вершины u. Радиусом r(G) графа G называется минимальный эксцентриситет графа
Диаметром d(G) графа G называется максимальный эксцентриситет графа
Определение. Вершина u называется центральной, если e(u) = r(G). Множество всех центральных вершин неориентированного графа называют его центром. Вершина u называется периферийной, если e(u) = d(G).
Заметим, что для любого неориентированного графа справедливо следующее соотношение: r(G) меньше либо равно d(G).
Заметим, что в полном графе радиус графа совпадает с диаметром графа, равным единице d(Kn) = r(Kn) = 1, а в неориентированном графе, имеющем простые циклы длины n, радиус графа совпадает с диаметром графа, равным n\2.
Пример 3. Определим радиус и диаметр неориентированных графов G1– G3, показанных на рис. выше. Какие вершины являются центральными, периферийными?
Для неориентированного графа G1 имеем e(a) = e(b) = e(e) = e(f) = 3, e(c) = e(d) = 2, следовательно, получаем радиус графа G1, равный 2, диаметр графа G1, равный 3. Следовательно, центральными вершинами являются вершины cи d, а периферийными вершинами – a, b, e, f.
Для неориентированного графа G2 имеем e(a) = e(b) = 4, e(c) = e(e) = e(f) = 3, e(d) = 2, следовательно, получаем радиус графа G2, равный 2, диаметр графа G1, равный 4. Следовательно, центральной вершиной является вершина d, а периферийными вершинами – a и b.
Для неориентированного графа G3 получаем: r(G3) = d(G3) = 0. Следовательно, центральной вершиной графа G3 является вершина, являющаяся также периферийной, т.е. вершина a.
В качестве Упражнения предлагается
1) определить расстояние заданного неориентированного графа (варианты ниже);
2) задать произвольным образом веса заданного неориентированного графа и записать матрицу расстояний;
3) определить радиус и диаметр.
Варианты неориентированных графов: