14
правок
Изменения
→Леммы
== Леммы ==
{{Лемма|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> будет <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 2</tex>.
Рассмотрим любую пару смежных вершин <tex>u = (u_1, u_2)</tex> и <tex>v = (v_1, v_2)</tex> из графа <tex>G</tex>, два случая:
Следовательно каждое ребро графа <tex>G</tex> соединяет вершины разного цвета, значит <tex>G</tex> двудольный.
}}
== Источники информации ==
* Харари Ф. Теория графов / пер. с англ. — изд. 1-ое, с.35
