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

''Декартово'' произведение <math>G =

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

E^{2}.</math>

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

все ребра

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

''Композиция''

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

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

и <math>(x^{2},y^{2}) \in E_{2}.</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>G_{1} \Diamond G_{2}</math>содержит

ребра

только тогда, когда

<math>x^{1} \neq y^{1}</math> <math>x^{2} \neq y^{2}</math>и либо