Произведение графов

Произведение графов (Product of graphs) — для данных графов [math]\displaystyle{ \,G_{1} = (V_{1}, E_{1}) }[/math] и [math]\displaystyle{ \,G_{2} = (V_{2}, E_{2}) }[/math] произведением называется граф [math]\displaystyle{ \,G = (V,E) }[/math], вершины которого [math]\displaystyle{ V(G) = V_{1} \times V_{2} }[/math] — декартово произведение множеств вершин исходных графов.

Декартово произведение [math]\displaystyle{ G = G_{1} \Box G_{2} }[/math] содержит ребра

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \Box G_{2}) }[/math]

тогда и только тогда, когда [math]\displaystyle{ (x^{1},y^{1}) \in E_{1} }[/math] и [math]\displaystyle{ \,x^{2} = y^{2} }[/math] или [math]\displaystyle{ \,x^{1} = y^{1} }[/math] и [math]\displaystyle{ (x^{2},y^{2}) \in E_{2}. }[/math]

Прямое (тензорное) произведение [math]\displaystyle{ G = G_{1} \times G_{2} }[/math] содержит ребра

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \times G_{2}) }[/math]

тогда и только тогда, когда [math]\displaystyle{ (x^{1},y^{1}) \in E_{1} }[/math] и [math]\displaystyle{ (x^{2},y^{2}) \in E^{2}. }[/math]

Сильное произведение [math]\displaystyle{ G = G_{1} \otimes G_{2} }[/math] содержит все ребра

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \otimes G_{2}), }[/math]

которые есть и в декартовом, и в тензорном произведениях.

Композиция [math]\displaystyle{ \,G_{1}[G_{2}] }[/math] графов содержит ребра

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1}[G_{2}]) }[/math]

тогда и только тогда, когда [math]\displaystyle{ (x^{1},y^{1}) \in E_{1} }[/math] или [math]\displaystyle{ x^{1} = y^{1} }[/math] и [math]\displaystyle{ (x^{2},y^{2}) \in E_{2}. }[/math]

Модульное произведение [math]\displaystyle{ G_{1} \diamondsuit G_{2} }[/math] содержит ребра

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \diamondsuit G_{2}) }[/math]

тогда и только тогда, когда [math]\displaystyle{ x^{1} \neq y^{1} }[/math] [math]\displaystyle{ x^{2} \neq y^{2} }[/math] и либо [math]\displaystyle{ (x^{1},y^{1}) \in E_{1} }[/math] и [math]\displaystyle{ (x^{2},y^{2}) \in E_{2}, }[/math] либо [math]\displaystyle{ (x^{1},y^{1}) \not \in E_{1} }[/math] и [math]\displaystyle{ (x^{2},y^{2}) \not \in E_{2}. }[/math]

Большое модульное произведение [math]\displaystyle{ G_{1} \Diamond G_{2} }[/math] содержит ребра

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \Diamond G_{2}) }[/math]

тогда и только тогда, когда [math]\displaystyle{ x^{1} \neq y^{1} }[/math] [math]\displaystyle{ x^{2} \neq y^{2} }[/math] и либо [math]\displaystyle{ (x^{1},y^{1}) \in E_{1} }[/math] и [math]\displaystyle{ (x^{2},y^{2}) \in E_{2}, }[/math] либо [math]\displaystyle{ (x^{1},y^{1}) \not \in E_{1}. }[/math]

См. также

• Декартово произведение графов.

Литература

• Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.

• Оре О. Теория графов. — М.: Наука, 1968.

• Харари Ф. Теория графов. — М.: Мир, 1973.

• Berge C. Graphs (second revised edition). — Amsterdam; New York; Oxford: North-Holland, 1985.

• Bondy J.A., Murty U.S.R. Graph theory with applications. — New York; Amsterdam; Oxford: North-Holland, 1976.