Характеристики графов
Пусть G(X) – конечный или бесконечный ориентированный граф. Отклонением d(xi, xj) его вершины xi от вершины xj называется длина кратчайшего пути из хi в xj:
d(xi, xj) = min {l[Sk(xi, xj)]}.
Отклонение d(xi, xj) удовлетворяет следующим аксиомам метрического пространства:
1. d(xi, xj) ³ 0;
2. d(xi, xj) = 0 Û xi = xj;
3. d(xi, xj) + d(xj, xk) ³ d(xi, xk) – неравенство треугольника и не удовлетворяет четвертой аксиоме, а именно:
4. d(xi, xj) ¹ d(xj, xi), так как граф ориентирован.
Необходимо отметить, что если xj Ï G(xi), то d(xi, xj) = ¥. Отклоненностью вершины xi называется наибольшее из отклонений d(xi, xj) по всем xj:
.
В качестве примера рассмотрим схему первой (1870 г.) сети связи для почтовых голубей (рис. 3.29).
Рис. 3.29. Схема первой сети связи для почтовых голубей
Граф, представляющий ее, изображен на рис. 3.29, а матрица отклонений и вектор отклоненностей – в табл. 3.2 и табл. 3.3 соответственно.
Таблица 3.2. Отклонения d(xi, xj)
Города | П | Б | Л | Г | М | Н |
Париж | ||||||
Бордо | ||||||
Лион | ||||||
Гренобль | ¥ | ¥ | ¥ | ¥ | ||
Марсель | ||||||
Ницца | ¥ | ¥ | ¥ | ¥ | ¥ |
Таблица 3.3. Вектор отклонений
|
|
Города | П | Б | Л | Г | М | Н | |
d(xi) | ¥ | ¥ |
Для неориентированного графа, соответствующего графу, изображенному на рис. 3.29, можно найти аналогичные характеристики, но без учета ориентации дуг. При этом матрица d(xi, xj) оказывается симметричной.
В связном неориентированном графе понятиям отклонения и отклоненности соответствуют понятия: расстояние и удаленность.
Пусть G(X) – связный неориентированный граф. В соответствии с определением связности для вершин xi и xj графа существует элементарная цепь S(xi, xj) с концами xi и xj, причем l(S) ³ 0.
Расстоянием d(xi, xj) между вершинами xi и xj называется длина цепи S(xi, xj) наименьшей длины
.
Удаленность вершины xi графа G(X) есть число
.
Центром графа называется вершина, в которой достигается наименьшая из отклоненностей (удаленностей), если таковая является конечным числом. В графе может быть несколько центров (Париж, Лион), а может не быть ни одного.
Периферийной вершиной графа называется вершина с наибольшей отклоненностью или удаленностью (Гренобль, Ницца).
Радиусом p(G) ориентированного графа называется отклоненность его центра.
В примере (рис. 3.29) r(G) = 2 (d(П) = d(Л) = 2). Если в графе нет центров, то полагают, что r(G) = ¥. В неориентированном графе r(G) – удаленность центра.
Диаметром неориентированного графа называется удаленность периферийной вершины.