14
правок
Изменения
Нет описания правки
__TOC__
==Определения==
Пусть графы <tex>G_1</tex> и <tex>G_2</tex> имеют непересекающиеся множества вершин <tex>V_1</tex> и <tex>V_2</tex> и непересекающиеся множества ребер <tex>X_1</tex> и <tex>X2</tex>.
=== Объединение ===
{{Определение
|id = obedinenie
'''Объединением''' <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
}}
[[Файл:соединение.png|thumb|1100px|center]]
=== Произведение ===
{{Определение
|id = proizvedenie
}}
[[Файл:произведение.png|thumb|1100px|center]]
=== Композиция ===
{{Определение
|id = compozicia
}}
[[Файл:композиция.png|thumb|1100px|center]]
== Леммы ==
=== Лемма о произведении регулярных графов ===
{{Теорема
|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> регулярный.
}}
=== Лемма о композиции регулярных графов ===
{{Теорема
|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| * k_1 + k_2</tex> смежных вершин. Значит граф <tex>G</tex> регулярный.
}}
=== Лемма о произведении двудольных графов ===
{{Теорема
|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> будет 0, а правых 1.
А цвет каждой вершины <tex>v = (v_1, v_2)</tex> графа <tex>G</tex> будет равен <tex>c(v) = (c(v_1) + c(v_2)) mod 2</tex>.
Рассмотрим любую пару смежных вершин <tex>u = (u_1, u_2)</tex> и <tex>v = (v_1, v_2)</tex> из графа <tex>G</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>.
Следовательно каждое ребро графа <tex>G</tex> соединяет вершины разного цвета, значит <tex>G</tex> двудольный.
}}
== Источники информации ==
* Харари Ф. Теория графов / пер. с англ. — изд. 1-ое, с.35
