4189
правок
Произведение графов: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Произведение графов''' (''Product of graphs'') - для данных графов <math>G_{1} = (V_{1}, E_{1})</math...) |
Glk (обсуждение | вклад) Нет описания правки |
||
| Строка 6: | Строка 6: | ||
''Декартово'' произведение <math>G = | ''Декартово'' произведение <math>G = | ||
G_{1} \Box G_{2}</math>содержит ребра <math>((x^{1},x^{2}), (y^{1},y^{2})) \in | G_{1} \Box G_{2}</math>содержит ребра | ||
E(G_{1} \Box G_{2})</math> тогда и только тогда, когда <math>(x^{1},y^{1}) \in | |||
<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_{1}</math>и <math>x^{2} = y^{2}</math>или <math>x^{1} = y^{1}</math> и <math>(x^{2},y^{2}) \in | ||
E_{2}.</math> | E_{2}.</math> | ||
| Строка 13: | Строка 17: | ||
''Прямое (тензорное)'' произведение <math>G = G_{1} \times G_{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},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>(x^{1},y^{1}) \in E_{1}</math> и <math>(x^{2},y^{2}) \in | ||
E^{2}.</math> | E^{2}.</math> | ||
| Строка 19: | Строка 26: | ||
''Сильное'' произведение <math>G = G_{1} \otimes G_{2}</math>содержит | ''Сильное'' произведение <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>((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \otimes G_{2}),</math> | |||
которые | |||
есть и в декартовом, и в тензорном произведениях. | есть и в декартовом, и в тензорном произведениях. | ||
''Композиция'' | ''Композиция'' | ||
<math>G_{1}[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},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>(x^{1},y^{1}) \in E_{1}</math>или <math>x^{1} = y^{1}</math> | ||
и <math>(x^{2},y^{2}) \in E_{2}.</math> | и <math>(x^{2},y^{2}) \in E_{2}.</math> | ||
| Строка 33: | Строка 46: | ||
''Модульное'' произведение <math>G_{1} \diamondsuit G_{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},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} \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}) \in E_{1}</math>и <math>(x^{2},y^{2}) \in E_{2},</math>либо | ||
| Строка 40: | Строка 55: | ||
''Большое модульное'' произведение <math>G_{1} \Diamond G_{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},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} \neq y^{1}</math> <math>x^{2} \neq y^{2}</math>и либо | ||