Файл: Diskretnaya_matematika.doc

Рис. 3.22. Пример графа для определения матрицS и R

3.4. Операции над графами

3.4.1. Сумма графов

Пусть даны два графа G₁(X) иG₂(X) на одном и том же множе­стве вершин. ТогдасуммойграфовG₁(X) иG₂(X) является графG(X), состоящий из ребер, принадлежащихG₁(X) илиG₂(X).

Таким образом, если (х_i', х_j')G₁(X) и (х_i",х_j")G₂(X), то (х_i', х_j')G(X) и (х_i", х_j")G(X)(х_i', х_j', х_i", х_j")X.

Символически сумму двух графов обозначают следующим об­разом: G(X) =G₁(X)G₂(X). Аналогично определяется суммаnграфовG_i(X) (i= 1, ...,n):

G(X) =

как граф, состоящий из ребер, принадлежащих хотя бы одному из графов G_i(X) (рис. 3.24).

Операция суммирования графов обладает перемес­тительным свойством: G₁(X)G₂(X) =G₂(X)G₁(X).

Рассмотрим случай, когда операция суммы графов применяется к графам, определенным на различных множествах вершин. Тогда суммой G(X) будет граф

G(X) = G₁(X₁)  G₂(X₂)  …  G_n (X_n) =,

для которого справедливо:

X = X₁  X₂  ...  X_n

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

Сумма графов G₁(X₁) и G₂(X₂) изображена на рис. 3.23.

Пример 1

Рис. 3.23. Суммирование графов с различными множествами вершин

Пример 2

Рис. 3.24. Суммирование графов с одинаковыми множествами вершин

3.4.2. Пересечение графов

Пусть даны два графа G₁(X) иG₂(X) на одном и том же множе­стве вершин. ТогдапересечениемграфовG₁(X) иG₂(X) называется графG(X), состоящий из ребер, принадлежащих иG₁(X) иG₂(X), то есть если (х_i, х_j)G₁(X) и (х_i, х_j)G₂(X), то (х_i, х_j)G(X).

Обозначение пересечения двух графов:

G(X) =G₁(X)G₂(X).

Аналогично пересечение 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: