Пример 2.3

На рис. 2.8. изображен граф с p = 3 компонентами связности.

Если граф G связен, то p = 1, то есть, сам граф является своей единственной компонентой связности. Для несвязного графа количество компонент связности p всегда больше 1.

 

 

Рис. 2.8. Несвязный граф, p = 3

 

Рис. 2.9. Точка сочленения, v

 

Пусть G некоторый граф, обозначим через S(v) звездный граф вершины v. Вершина v графа G называется точкой сочленения, если число компонент связности дополнения звездного графа  S(v) до графа G больше числа компонент связности графа G.

Иначе говоря, удаление вершины, являющейся точкой сочленения, вместе с инцидентными ей ребрами, увеличивает разбиение графа на компоненты связности.

Пример 2.4

На рис. 2.9 изображен граф с одной точкой сочленения (вершина v).

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

Пусть G – связный граф, v и w – любые две его вершины. Тогда существует соединяющая их простая цепь: M = v, e₁ ,…, e_i ,…, e_k , w. Если количество k ребер этой цепи не минимальное из возможных, то существует простая цепь M = v, e₁ ,…, e_i ,…, e_s , w  с меньшим числом ребер (s < k), соединяющая вершины v, w.   Если и в  M  количество ребер не минимально, можно найти соединяющую v и w простую цепь с еще меньшим количеством ребер и т.д. Однако процесс уменьшения числа ребер можно повторить не более k раз, так как это число каждый раз уменьшается не меньше чем на единицу. Поэтому существует соединяющая  v и w простая цепь M* = v, e*₁ ,…, e*_i ,…, e*_d , w с минимальным количеством ребер d.

Минимальная длина из возможных длин простых цепей с началом  v и концом  w называется расстоянием  d(v, w) между этими вершинами.

Понятие расстояния часто распространяют и на несвязные графы. При этом если вершины v и w несвязанны, то полагают: d(v, w) = .

Утверждение 2.5. Введенное понятие расстояния между двумя вершинами связного графа удовлетворяет аксиомам метрики:

1) d(v, w)  0, причем d(v, w) = 0 тогда и только тогда, когда v = w;

2) d(v, w) = d(w, v);

3) d(v, u) + d(u, w)   d(v, w) (справедливо неравенство треугольника);

4) d(v, w) < .

Доказательство

1) Считая каждую вершину v неориентированного графа связанной саму с собой, мы, по существу, ввели нулевые маршруты, не содержащие ребер, с началом и концом в любой вершине v  G. В соответствии с этим расстояние d(v, v) = 0. Для любой пары v, w  G различных вершин d(v, w) > 0, так как связывающая эти вершины простая цепь состоит хотя бы из одного ребра.

2) Любой маршрут, связывающий вершину v c w, записанный в обратном порядке, связывает так же и вершину w с v. Длины этих маршрутов равны.

3) Пусть M₁ – простая цепь минимальной длины, соединяющая вершины v и u, следовательно, L(M₁) = d(v, u), здесь через L(M₁) обозначена длина M₁ . Пусть M₂ – простая цепь минимальной длины, соединяющая вершины u и w, следовательно,  L(M₂) = d(u, w). Пусть M – простая цепь минимальной длины, соединяющая вершины v и w, следовательно, L(M) = d(v, w). Так как композиция  M₁  M₂ – некоторый в общем случае отличный от M маршрут, связывающий вершины v и w, то L(M₁M₂)  L(M) (по определению M). Отсюда имеем:

L(M₁   M₂) = L(M₁) + L(M₂) =d(v, u) + d(u, w)  L(M) = d(v, w).

4) Нет, не связанных вершин.

Диаметр, радиус и центр графа

Пусть G – конечный связный граф. Так как в графе определено расстояние, удовлетворяющее аксиомам метрики, то можно определить и другие метрические характеристики подобные характеристикам геометрических фигур.

Диаметром графа  G  называется конечная величина  , при этом простые цепи, связывающие вершины v, w  G и имеющие максимальную длину d(v, w), называются диаметральными. 

Пусть v  произвольная вершина рассматриваемого графа.

Максимальным удалением (эксцентриситетом) в графе G  от вершины v называется величина .

Радиусом графа G  называется величина .

Центром графа G называется вершина u,  такая, что r(u) = r(G), иначе говоря, вершина, доставляющая минимум максимальному удалению r(v). Любая простая цепь минимальной длины, связывающая вершины, в которых выполняется указанное равенство, называется радиальной цепью.

 

Рис. 2.10. Граф K₃

 

Центр графа не обязательно должен быть единственным. Например, в полном графе К_n , в котором любые две различные вершины v, w  соединены ребром, радиус равен единице и любая вершина u  V является центром.