Произведение графов: различия между версиями

'''Произведение графов''' (''[[Product of graphs]]'') —

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

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

:::<math>((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \Box G_{2})</math>  

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

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

:::<math>((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \times G_{2})</math>  

тогда и только тогда, когда <math>(x^{1},y^{1}) \in E_{1}</math> и <math>(x^{2},y^{2}) \in

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

:::<math>((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \otimes G_{2}),</math>  

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

<math>\,G_{1}[G_{2}]</math> графов содержит ребра

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

тогда и только тогда, когда <math>(x^{1},y^{1}) \in E_{1}</math> или <math>x^{1} = y^{1}</math>

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

:::<math>((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \diamondsuit G_{2})</math>  

тогда и только тогда, когда <math>x^{1} \neq y^{1}</math> <math> x^{2} \neq y^{2}</math> и либо

<math>(x^{1},y^{1}) \in E_{1}</math> и <math>(x^{2},y^{2}) \in E_{2},</math> либо

<math>(x^{1},y^{1}) \not \in  E_{1}</math> и <math>(x^{2},y^{2}) \not \in E_{2}.</math>

''Большое модульное'' произведение <math>G_{1} \Diamond G_{2}</math> содержит

:::<math>((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \Diamond G_{2})</math>  

тогда и только тогда, когда <math>x^{1} \neq y^{1}</math> <math>x^{2} \neq y^{2}</math> и либо

<math>(x^{1},y^{1}) \in E_{1}</math> и <math>(x^{2},y^{2}) \in E_{2},</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.