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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Произведение графов''' (''Product of graphs'') - для данных графов <math>G_{1} = (V_{1}, E_{1})</math...)
 
Нет описания правки
 
(не показаны 3 промежуточные версии 2 участников)
Строка 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>V(G) = V_{1} \times V_{2}</math> декартово произведение
произведением  называется граф <math>G = (V,E)</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
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} \Box 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}</math> или <math>\,x^{1} = y^{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
 
''Прямое (тензорное)'' произведение <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
E^{2}.</math>
E^{2}.</math>


''Сильное'' произведение <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},y^{1}) \in E_{1}</math>или <math>x^{1} = y^{1}</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^{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> содержит ребра
<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},x^{2}), (y^{1},y^{2})) \in E(G_{1} \diamondsuit G_{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>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>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},y^{1}) \in E_{1}</math>и <math>(x^{2},y^{2}) \in E_{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^{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],
* Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.
 
[Берж],  


[Оре],  
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.


[Харари],  
* Оре О. Теория графов. — М.: Наука, 1968.


[Лекции],  
* Харари Ф. Теория графов. —  М.: Мир, 1973.


[Bondy-Murty]
* 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.

Текущая версия от 12:42, 8 июля 2011

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

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

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \Box G_{2}) }[/math]

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

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

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \times G_{2}) }[/math]

тогда и только тогда, когда [math]\displaystyle{ (x^{1},y^{1}) \in E_{1} }[/math] и [math]\displaystyle{ (x^{2},y^{2}) \in E^{2}. }[/math]

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

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \otimes G_{2}), }[/math]

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

Композиция [math]\displaystyle{ \,G_{1}[G_{2}] }[/math] графов содержит ребра

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

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

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

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \diamondsuit G_{2}) }[/math]

тогда и только тогда, когда [math]\displaystyle{ x^{1} \neq y^{1}, }[/math] [math]\displaystyle{ x^{2} \neq y^{2} }[/math] и либо [math]\displaystyle{ (x^{1},y^{1}) \in E_{1} }[/math] и [math]\displaystyle{ (x^{2},y^{2}) \in E_{2}, }[/math] либо [math]\displaystyle{ (x^{1},y^{1}) \not \in E_{1} }[/math] и [math]\displaystyle{ (x^{2},y^{2}) \not \in E_{2}. }[/math]

Большое модульное произведение [math]\displaystyle{ G_{1} \Diamond G_{2} }[/math] содержит ребра

[math]\displaystyle{ ((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \Diamond G_{2}) }[/math]

тогда и только тогда, когда [math]\displaystyle{ x^{1} \neq y^{1}, }[/math] [math]\displaystyle{ x^{2} \neq y^{2} }[/math] и либо [math]\displaystyle{ (x^{1},y^{1}) \in E_{1} }[/math] и [math]\displaystyle{ (x^{2},y^{2}) \in E_{2}, }[/math] либо [math]\displaystyle{ (x^{1},y^{1}) \not \in E_{1}. }[/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.