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>.
=== Объединение ===
[[Файл:композиция.png|thumb|1100px|center]]
{{Лемма
|about=
<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> будет <text>0</tex>, а правых <tex>1</text>.А цвет каждой вершины <tex>v = (v_1, v_2)</tex> графа <tex>G</tex> будет равен <tex>c(v) = (c(v_1) + c(v_2)) mod \bmod 2</tex>.
Рассмотрим любую пару смежных вершин <tex>u = (u_1, u_2)</tex> и <tex>v = (v_1, v_2)</tex> из графа <tex>G</tex>, два случая:
