Теоретико-множественные операции над графами

Определения

Пусть графы [math]G_1[/math] и [math]G_2[/math] имеют непересекающиеся множества вершин [math]V_1[/math] и [math]V_2[/math] и непересекающиеся множества ребер [math]X_1[/math] и [math]X2[/math].

Объединение

Определение:

Объединением (англ. union) [math]G_1 \cup G_2[/math] называется граф, множеством вершин которого является [math]V=V_1 \cup V_2[/math], а множество ребер [math]X=X_1 \cup X_2[/math].

Соединение

Определение:

Соединением (англ. graph join) [math]G_1 + G_2[/math] называется граф, который состоит из [math]G_1 \cup G_2[/math] и всех ребер, соединяющих [math]V_1[/math] и [math]V_2[/math].

Произведение

Определение:

Произведением (англ. cartesian product) [math]G_1 \times G_2[/math] называется граф с множеством вершин [math]V[/math] равным декартовому произведению [math]V_1 \times V_2[/math]. Множество ребер [math]X[/math] определяется следующим образом: Рассмотрим любые две вершины [math]u=(u_1, u_2)[/math] и [math]v=(v_1, v_2)[/math] из [math]V=V_1 \times V_2[/math]. Вершины [math]u[/math] и [math]v[/math] смежны в [math]G=G_1 + G_2[/math] тогда и только тогда, когда ([math]u_1 = v_1[/math], а [math]u_2[/math] и [math]v_2[/math] - смежные) или ([math]u_2 = v_2[/math], а [math]u_1[/math] и [math]v_1[/math] - смежные).

Композиция

Определение:

Композицией (англ. lexicographical product) [math]G_1[G_2][/math] называется граф с множеством вершин [math]V[/math] равным декартовому произведению [math]V_1 \times V_2[/math]. Множество ребер [math]X[/math] определяется следующим образом: Так же рассмотрим любые две вершины [math]u=(u_1, u_2)[/math] и [math]v=(v_1, v_2)[/math] из [math]V=V_1 \times V_2[/math]. Вершины [math]u[/math] и [math]v[/math] смежны в [math]G=G_1 + G_2[/math] тогда и только тогда, когда ([math]u_1[/math] и [math]v_1[/math] - смежные) или ([math]u_1 = v_1[/math], а [math]u_2[/math] и [math]v_2[/math] - смежные).

Леммы

Лемма о произведении регулярных графов

Теорема:

[math]G_1[/math] и [math]G_2[/math] - регулярные графы. Тогда [math]G = G_1 \times G_2[/math] - регулярный граф.

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

[math]\triangleright[/math]

Пусть степень графов [math]G_1[/math] и [math]G_2[/math] будут [math]k_1[/math] и [math]k_2[/math] соответственно. Рассмотрим любую вершину графа [math]G[/math]: у нее [math]k_1 + k_2[/math] смежных вершин. Значит граф [math]G[/math] регулярный.

[math]\triangleleft[/math]

Лемма о композиции регулярных графов

Теорема:

[math]G_1[/math] и [math]G_2[/math] - регулярные графы. Тогда [math]G = G_1[G_2][/math] - регулярный граф.

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

[math]\triangleright[/math]

Пусть степень графов [math]G_1[/math] и [math]G_2[/math] будут [math]k_1[/math] и [math]k_2[/math] соответственно. Рассмотрим любую вершину графа [math]G[/math]: у нее [math]|V_2| * k_1 + k_2[/math] смежных вершин. Значит граф [math]G[/math] регулярный.

[math]\triangleleft[/math]

Лемма о произведении двудольных графов

Теорема:

[math]G_1[/math] и [math]G_2[/math] - двудольные графы. Тогда [math]G = G_1 \times G_2[/math] - двудольный граф.

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

[math]\triangleright[/math]

Пусть цвет [math]c[/math] левых долей [math]G_1[/math] и [math]G_2[/math] будет 0, а правых 1. А цвет каждой вершины [math]v = (v_1, v_2)[/math] графа [math]G[/math] будет равен [math]c(v) = (c(v_1) + c(v_2)) mod 2[/math]. Рассмотрим любую пару смежных вершин [math]u = (u_1, u_2)[/math] и [math]v = (v_1, v_2)[/math] из графа [math]G[/math], два случая: 1. [math]u_1 = v_1[/math], [math]u_2[/math] и [math]v_2[/math] - смежные, значит [math]c(u_1) = c(v_1)[/math] и [math]с(u_2) \ne c(v_2)[/math], из этого следует [math]c(u) \ne c(v)[/math]. 2. [math]u_2 = v_2[/math], [math]u_1[/math] и [math]v_1[/math] - смежные, аналогично следует [math]c(u) \ne c(v)[/math]. Следовательно каждое ребро графа [math]G[/math] соединяет вершины разного цвета, значит [math]G[/math] двудольный.

[math]\triangleleft[/math]

Источники информации

• Харари Ф. Теория графов / пер. с англ. — изд. 1-ое, с.35