Аноним

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

Материал из WikiGrapp
нет описания правки
(Создана новая страница размером '''Произведение графов''' (''Product of graphs'') - для данных графов <math>G_{1} = (V_{1}, E_{1})</math...)
 
Нет описания правки
Строка 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>и либо
4189

правок