Изменения

__TOC__

{{Определение

|id = obedinenie

'''Объединением''' (англ. ''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

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

}}

{{Определение

|id = proizvedenie

* вершины <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> — смежные).

}}

{{Определение

|id = compozicia

* вершины <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> — смежные).

}}

{{Лемма

|about=

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

|proof=

Рассмотрим любую пару смежных вершин <tex>u = (u_1, u_2)</tex> и <tex>v = (v_1, v_2)</tex> из графа <tex>G</tex>, два случая: