14
правок
Изменения
Нет описания правки
__TOC__ Пусть [[Основные_определения_теории_графов|графы ]] <tex>G_1</tex> и <tex>G_2</tex> имеют непересекающиеся множества вершин <tex>V_1</tex> и <tex>V_2</tex> и непересекающиеся множества ребер <tex>X_1</tex> и <tex>X2X_2</tex>.
{{Определение
|id = obedinenie
|definition =
'''Объединением''' (англ. ''union'') <tex>G_1 \cup G_2</tex> называется граф, множеством вершин которого является <tex>V=V_1 \cup V_2</tex>, а множество ребер <tex>X=X_1 \cup X_2</tex>.
}}
{{Определение
|id = soedinenie
|definition =
'''Соединением''' (англ. ''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>]]
{{Определение
|id = proizvedenie
|definition =
'''Произведением''' (англ. ''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>]]
{{Определение
|id = compozicia
|definition =
'''Композицией''' (англ. ''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=
о произведении регулярных графов
|statement=
<tex>G_1</tex> и <tex>G_2</tex> — [[Основные_определения_теории_графов|регулярные]] графы. Тогда <tex>G = G_1 \times G_2</tex> — регулярный граф.
|proof=
Пусть степень графов <tex>G_1</tex> и <tex>G_2</tex> будут <tex>k_1</tex> и <tex>k_2</tex> соответственно.
Рассмотрим любую вершину графа <tex>G</tex>: у нее <tex>k_1 + k_2</tex> смежных вершин. Значит граф <tex>G</tex> регулярный.
}}
{{Лемма
|about=
о композиции регулярных графов
|statement=
<tex>G_1</tex> и <tex>G_2</tex> — регулярные графы. Тогда <tex>G = G_1[G_2]</tex> — регулярный граф.
|proof=
Пусть степень графов <tex>G_1</tex> и <tex>G_2</tex> будут <tex>k_1</tex> и <tex>k_2</tex> соответственно.
Рассмотрим любую вершину графа <tex>G</tex>: у нее <tex>|V_2| \cdot k_1 + k_2</tex> смежных вершин. Значит граф <tex>G</tex> регулярный.
}}
{{Лемма
|about=
о произведении двудольных графов
|statement=
<tex>G_1</tex> и <tex>G_2</tex> — [[Основные_определения_теории_графов|двудольные]] графы. Тогда <tex>G = G_1 \times G_2</tex> — двудольный граф.
|proof=
Пусть цвет <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)) \bmod 2</tex>.
Рассмотрим любую пару смежных вершин <tex>u = (u_1, u_2)</tex> и <tex>v = (v_1, v_2)</tex> из графа <tex>G</tex>, два случая:
# <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>,
# <tex>u_2 = v_2</tex>, <tex>u_1</tex> и <tex>v_1</tex> — смежные, аналогично следует <tex>c(u) \ne c(v)</tex>.
Следовательно каждое ребро графа <tex>G</tex> соединяет вершины разного цвета, значит <tex>G</tex> двудольный.
}}
==См. также==
* [[Дополнительный, самодополнительный граф]]
* [[Дерево, эквивалентные определения]]
== Источники информации ==
* Харари Ф. Теория графов / пер. с англ. — изд. 1-ое, с.35
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Основные определения теории графов]]
