Изменения

==Определения==Пусть [[Основные_определения_теории_графов|графы ]] <tex>G_1</tex> и <tex>G_2</tex> имеют непересекающиеся множества вершин <tex>V_1</tex> и <tex>V_2</tex> и непересекающиеся множества ребер <tex>X_1</tex> и <tex>X2X_2</tex>.=== Объединение ===

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

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

[[Файл:соединение.png|thumb|1100px|center|Соединение <tex>G_1</tex> и <tex>G_2</tex>]]=== Произведение ===

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

[[Файл:произведение.png|thumb|1100px|center|Произведение <tex>G_1</tex> и <tex>G_2</tex>]]=== Композиция ===

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

[[Файл:композиция.png|thumb|1100px|center|Композиция <tex>G_1</tex> и <tex>G_2</tex>]]== Леммы ={{Лемма|about==== Лемма о произведении регулярных графов ==={{Теорема

<tex>G_1</tex> и <tex>G_2</tex> - — [[Основные_определения_теории_графов|регулярные ]] графы. Тогда <tex>G = G_1 \times G_2</tex> - — регулярный граф.

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

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

Рассмотрим любую вершину графа <tex>G</tex>: у нее <tex>|V_2| * \cdot k_1 + k_2</tex> смежных вершин. Значит граф <tex>G</tex> регулярный.

 {{Лемма|about=== Лемма о произведении двудольных графов ==={{Теорема

<tex>G_1</tex> и <tex>G_2</tex> - — [[Основные_определения_теории_графов|двудольные ]] графы. Тогда <tex>G = G_1 \times G_2</tex> - — двудольный граф.

Пусть цвет <tex>c</tex> левых долей <tex>G_1</tex> и <tex>G_2</tex> будет <tex>0</tex>, а правых <tex>1</tex>.А цвет каждой вершины <tex>v = (v_1, v_2)</tex> графа <tex>G</tex> будет равен <tex>c(v) = (c(v_1) + c(v_2)) mod \bmod 2</tex>.

1. # <tex>u_1 = v_1</tex>, <tex>u_2</tex> и <tex>v_2</tex> - — смежные, значит <tex>c(u_1) = c(v_1)</tex> и <tex>с(u_2) \ne c(v_2)</tex>, из этого следует <tex>c(u) \ne c(v)</tex>.,2. # <tex>u_2 = v_2</tex>, <tex>u_1</tex> и <tex>v_1</tex> - — смежные, аналогично следует <tex>c(u) \ne c(v)</tex>.