Декартова сумма графов

Декартовой суммой графов G₁(x₁) и G₂(x₂) G(x) = G₁(x₁) + G₂(x₂) на­зывается граф, определенный следующим образом:

а) множество вершин X является декартовым произведением X₁ и X₂, т.е. X = X₁  X₂ = {(x_i1, x_j2) / x_i1  X₁, x_j2  X₂};

б) множество вершин, смежных с вершиной (x_i1, x_j2) определяется как

G(x_i1, x_j2) = [G₁(x_i1)  {x_j2}]  [{x_i1}  G₂(x_j2)] (  операция декартова про­изведения).

Для примера 5

G(x₀₁, x₀₂) = {G₁(x₀₁)  {x₀₂}}  {{x₀₁}  G₂(x₀₂)} =

={(x₁₁, x₀₂), (x₂₁, x₀₂)}  {(x₀₁, x₁₂)},

G(x₀₁, x₁₂) = {G₁(x₀₁)  {x₁₂}}  {{x₀₁}  G₂(x₁₂)}=

= {(x₁₁, x₁₂),(x₂₁, x₁₂)}  {(x₀₁, x₀₂)},

G(x₁₁,x₀₂) = {(x₀₁, x₀₂)}  {(x₁₁, x₁₂)}, G(x₁₁, x₁₂) = {(x₀₁, x₁₂)}  {(x₁₁, x₀₂)},

G(x₂₁,x₀₂) = {(x₀₁, x₀₂)}  {(x₂₁, x₁₂)}, G(x₂₁, x₁₂) = {(x₀₁, x₁₂)}  {(x₂₁, x₀₂)}.

Соответствующий граф изобра­жен на рис. 2.33.

Граф G(X) называется декарто­вой суммой n графов

G(X) = G₁(X₁) + G₂(X₂) + ... + G_n(X_n), если

а) X = X₁  X₂  ...  X_n;

б) G(x₁, x₂, ... , x_n) = [G₁(x₁)  {x₂}  ...  {x_n}]  [{x₁}  G₂(x₂)  ...  {x_n}]  ...  [{x₁}  {x₂}  ...  G_n(x_n)].

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

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

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

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

Очевидно, что m(x_i) = .

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

(1)

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

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

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

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

Конечные однородные графы могут быть представлены в виде пра­вильных многогранников (Платоновых тел): тетраэдра, куба, октаэдра, додекаэдра, икосаэдра и т.д. Примеры бесконечных однородных графов изображены на рис. 2.34.

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

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

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

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

Аналогом кратности неориентированных ребер 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, определится суммой ,

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

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

.

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

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