Материал: Diskretnaya_matematika

Аналогично пересечение nграфовG_i(X) (i= 1, ...,n) обознача­ется какG(X) =и определяет графG(X), состоящий из ребер, принадлежащих всем графамG_i(X).

Для графов примера 2 (рис. 3.24) имеем:

а) пересечение G₁(X)G₂(X) =(ноль-граф);

б) пересечение G₁(X) G₂(X) (рис. 3.25).

Для графов, определенных на различных множествах вершин операция пересечения определяется следующим образом:

G(X) = G₁(X₁)  G₂(X₂)  …  G_n (X_n) =

где X = X₁  X₂  ...  X_n =

иG(х_j) = G₁(х_j)  G₂(х_j)  …  G_n(х_j) =, х_j  Х.

3.5. Степени графов

3.5.1. Степени неориентированных графов

Пусть G(X) – неориентированный граф.Степеньюm(х)графаG(X) в вершине х называется число ребер, инцидентных вершине х. Если все числаm(х) для хXконечны, то граф называетсяло­кально конечным. Петли можно считать одинарным или двойным ребром в зависимости от конкретной задачи.

Обозначим m(х_i, x_j) =m(x_j, х_i) – число ребер, соеди­няющих вершины х_iиx_j. Если в графеG(X) нет кратных ребер, тоm(х_i, x_j) = 0 илиm(х_i, x_j) =l.

Очевидно, что

m(х_i) =

Поскольку каждое ребро учитывается в двух вершинах х_iиx_j, то общее число реберmграфаG(X):

. (7)

Это выражение справедливо и для графов с петлями, если пет­лю считать двойным ребром.

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

Граф, степени всех вершин в котором равны, называется одно­родным, т.е.m(x_i) =m_nx_iX.

Из (7) следует, что в однородном графе степениm_n, число ребер равно гдеn- число вершин.

Рис. 3.27. Бесконечные однородные графы

3.5.2. Степени ориентированных графов

В ориентированном графе существуют такие понятия, как по­лустепени исхода и захода.

Полустепенью исхода m'(х) называется число дуг, выхо­дящих из вершины х. Полустепень захода m"(х) – число дуг, входящих в вершину х. Петли считают по одному разу в каждой из полустепе­ней.

Аналогом кратности неориентированных ребер m(x_i,x_j) в ори­ентированном графе являются две кратности:m'(x_i, x_j) – число дуг, направленных отx_iкx_j,m"(x_i,x_j) – число дуг, направленных отx_jкx_i.

Таким образом:

m'(x_i, x_j) = m"( x_j, x_i).

Число дуг, выходящих из вершины x_i, определится суммой

а число дуг, входящих в вершину х_i равно

Отсюда общее число дуг графа:

Если все полустепени m'(x) иm"(x) равны для всех хX, то ориентированный графG(X) называетсяоднородным графомстепениm_n.

Рис. 3.28. Однородные ориентированные графы

Для такого графа m=m_nхn, гдеnчисло вершин графаG(X). Примеры однородных ориентированных графов приве­дены на рис. 3.28.

3.6. Характеристики графов

3.6.1. Характеристики расстояний в графах

Пусть G(X) – конечный или бесконечный ориенти­рованный граф.Отклонениемd(x_i,x_j) его вершиныx_iот вершиныx_jназыва­ется длина кратчайшего пути из х_iвx_j:

d(x_i,x_j) =min{l[S_k(x_i,x_j)]}.

Отклонение d(x_i,x_j) удовлетворяет следующим аксио­мам мет­рического пространства:

1. d(x_i, x_j)  0;

2. d(x_i, x_j) = 0  x_i = x_j;

3. d(x_i, x_j) + d(x_j, x_k)  d(x_i, x_k) – неравенство треуголь­ника и не удовлетворяет четвертой аксиоме, а именно:

4. d(xi, xj)  d(xj, xi), так как граф ориентирован.

Необходимо отметить, что если x_j  G(x_i), то d(x_i, x_j) = . Отклоненностью вершины x_i называется наибольшее из от­клонений d(x_i, x_j) по всем x_j:

.

В качестве примера рассмотрим схему первой (1870 г.) сети связи для почтовых голубей (рис. 3.29).

Рис. 3.29. Схема первой сети связи для почтовых голубей

Граф, пред­став­ляющий ее, изображен на рис. 3.29, а матрица отклонений и вектор отклоненностей – в табл. 3.2 и табл. 3.3 соответственно.

Таблица 3.2. Отклонения d(x_i,x_j)

Таблица 3.3. Вектор отклонений

Для неориентированного графа, соответствующего графу, изо­браженному на рис. 3.29, можно найти аналогичные характеристики, но без учета ориентации дуг. При этом матрица d(x_i,x_j) оказывается симметричной.

В связном неориентированном графе понятиям отклонения и отклоненности соответствуют понятия: расстояниеиудаленность.

Пусть G(X) – связный неориентированный граф. В соответст­вии с определением связности для вершинx_iиx_jграфа существует элементарная цепьS(x_i,x_j) с концамиx_iиx_j, причемl(S)0.

Расстояниемd(x_i,x_j) между вершинамиx_iиx_jназывается дли­на цепиS(x_i,x_j) наименьшей длины

.

Удаленность вершины x_i графа G(X) есть число

.

Центромграфа называется вершина, в которой достигается наименьшая из отклоненностей (удаленностей), если таковая являет­ся конечным числом. В графе может быть несколько центров (Париж, Лион), а может не быть ни одного.

Периферийной вершинойграфа называется вершина с наи­большей отклоненностью или удаленностью (Гренобль, Ницца).

Радиусомp(G) ориентированного графа называется отклоненность его центра.

В примере (рис. 3.29) (G) = 2 (d(П) =d(Л) = 2). Если в графе нет центров, то полагают, что(G) =. В неориентированном графе(G) – удаленность центра.

Диаметромнеориентированного графа называется удален­ность периферийной вершины.