Произведение графов

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \Box G_{2})

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

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

((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \times G_{2})

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

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

((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \otimes G_{2}),

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

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

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

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

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

((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \diamondsuit G_{2})

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

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

((x^{1},x^{2}), (y^{1},y^{2})) \in E(G_{1} \Diamond G_{2})

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


См. также

Литература

  • Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 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.