5.8. Расстояние в графах

В неориентированном графе длина кратчайшего маршрута между вершинами и , если он существует, называется расстоянием между этими вершинами и обозначается как . Очевидно, что введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

(симметричность),

(неравенство треугольника).

Матрица D=(d_ij), в которой d_ij=d(v_i,v_j), называется матрицей расстояний. Заметим, что матрица D симметрична, т. е. D^T=D. Для фиксированной вершины , величина называется эксцентриситетом вершины . Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее вершины. Если D – матрица расстояний, то эксцентриситет е(v_i) равен наибольшему из чисел, стоящих в i-й строке.

Максимальный эксцентриситет вершин графа называется диаметром графа G и обозначается diam(G). Минимальный из всех эксцентриситетов вершин графа называется радиусом графа G r(G): r(G) = min{e(v_i)|v_iV}. Вершина v_i называется центральной, если е(x_i)=r(G). Множество всех центральных вершин графа называется его центром. Вершина v_i называется периферийной, если ее эксцентриситет равен диаметру графа.

П ример 5.1. Найдем центр и диаметр графа G, изображенного на рис. 22.

Матрица расстояний D имеет вид

_.

Матрица D позволяет найти эксцентриситеты как максимальные значения по строкам: е(1)=3, е(2)=2, е(3)=3, е(4)=2, е(5)=2 и, следовательно, diam(G)=3. Вершины и являются периферийными. Радиус графа, показанного на рис. 22, равен 2, а его центром является множество { , , }.

В полном графе К_п все различные вершины смежны, и поэтому diam(K_n) = r(К_n) = 1.

Задача нахождения центральных вершин возникает, например, если требуется оптимально разместить больницы, пункты обслуживания и т. п. В подобных ситуациях оптимизация заключается в минимизации расстояния от места обслуживания до наиболее удаленного населенного пункта.

5.9. Связность в неориентированных графах

Две вершины неорграфа графа называются связными, если существует маршрут, их связывающий. Неориентированный граф G(V, E) называется связным, если для любой пары вершин , существует соединяющая их цепь.

Любой граф G можно разбить на непересекающиеся подмножества вершин по признаку связности. Вершины одного множества являются связными между собой, а вершины различных множеств оказываются несвязны. Все выделенные таким образом подграфы называют компонентами связности графа G. Граф, имеющий одну компоненту связности, называется связным графом. Если свойство связности не выполняется, граф называется несвязным. Компонентой связности неориентированного графа G(V, E) называется максимальный связный подграф, т.е. не являющийся подграфом любого другого связного подграфа.

Отношение связности разбивает множество вершин на классы эквивалентности (компоненты связности).

Чтобы граф с n вершинами был связным, он должен иметь не менее (n-1) рёбер.

Теорема. Если неориентированный простой граф G имеет n вершин и k связных компонент, то максимальное число ребер в G равно

.

Если граф связный и без циклов (то есть это дерево), то удаление любого ребра приведёт к потере связности.

Свойство связности вершин неорграфа графа описывается квадратной матрицей связности S = [s_ij] порядка n, где n - число вершин. Элементы матрицы связности могут принимать значение 1, если существует цепь, соединяющая вершины v_i и v_j, или значение 0, если не существует цепи, соединяющей вершины v_i и v_j..

Матрица связности неориентированного графа является симметрической, и может быть приведена к блочно-диагональному виду, как, например, для графа, представленного на рис. 23.

Вершина называется шарниром (или точкой сочленения), если при ее удалении число компонент связности увеличивается. Ребро, при удалении которого увеличивается число компонент связности, называется перешейком (мостом). У графа, изображенного на рис. 24, вершина является шарниром, а ребро ( , ) является мостом.