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

Перейти к навигации Перейти к поиску

Произведение графов (посмотреть исходный код)

Версия от 17:48, 24 декабря 2009

445 байт убрано ,  24 декабря 2009
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Произведение графов''' (''Product of graphs'') -  
'''Произведение графов''' (''[[Product of graphs]]'') -  
для данных графов <math>G_{1} = (V_{1}, E_{1})</math> и <math>G_{2} = (V_{2}, E_{2})</math>
для данных [[граф|графов]] <math>G_{1} = (V_{1}, E_{1})</math> и <math>G_{2} = (V_{2}, E_{2})</math>
произведением  называется граф <math>G = (V,E)</math>, вершины которого
произведением  называется граф <math>G = (V,E)</math>, [[вершина|вершины]] которого
<math>V(G) = V_{1} \times V_{2}</math>--- декартово произведение
<math>V(G) = V_{1} \times V_{2}</math>--- декартово произведение
множеств вершин исходных графов.
множеств вершин исходных графов.


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


<math>((x^{1},x^{2}), (y^{1},y^{2})) \in
<math>((x^{1},x^{2}), (y^{1},y^{2})) \in
Строка 40: Строка 40:
тогда, когда <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>
%На рис. 1 можно видеть примеры произведений
%графов <math>G_{1} \Box G_{2}, \; G_{1} \times G_{2}, \; G_{1} \otimes
%G_{2}, \; G_{1}[G_{2}]</math>для <math>G_{1} \cong P_{2}</math>и <math>G_{2} \cong P_{3}</math>
%


''Модульное'' произведение <math>G_{1} \diamondsuit G_{2}</math>содержит ребра
''Модульное'' произведение <math>G_{1} \diamondsuit G_{2}</math>содержит ребра
Строка 63: Строка 59:
<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>либо
<math>(x^{1},y^{1}) \not \in  E_{1}.</math>
<math>(x^{1},y^{1}) \not \in  E_{1}.</math>
%
%На рис.2 можно увидеть примеры произведений графов <math>G_{1} \diamondsuit
%G_{2}</math>и <math>G_{1} \Diamond G_{2}</math>для <math>G_{1} \cong P_{3}</math>и <math>G_{2} =
%\bar{P}_{3}</math>.


См. также ''Декартово произведение графов''.
 
==См. также ==
''[[Декартово произведение графов]]''.
==Литература==
==Литература==
[Berge],  
[Berge],  
Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/4167

Навигация