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