Сильное произведение графов

Граф ходов короля, сильное произведение двух путей

Сильное произведение ${\displaystyle G\boxtimes H}$ графов G и H — это граф, такой, что^[1]:

• множество вершин ${\displaystyle G\boxtimes H}$ является прямым произведением ${\displaystyle V(G)\times V(H)}$
• различные вершины (u,u' ) и (v,v' ) связаны ребром в ${\displaystyle G\boxtimes H}$ тогда и только тогда, когда
  • u = v и u' смежна с v' , или
  • u' = v' и u смежна с v, или
  • u смежна с v и u' смежна с v' .

Сильное произведение является объединением прямого произведения и тензорного произведения.

Сильное произведение называется также нормальным произведением или AND произведением. Произведение впервые ввёл Сабидусси в 1960 году^[2]. Сильное произведение контрастирует со слабым произведением, но эти два произведения отличаются, только если применяются к бесконечным графам.

Например, граф ходов короля, граф, в котором вершинами являются клетки шахматной доски, а рёбра представляют возможные ходы короля, является сильным произведением двух путей^[3].

Следует проявлять осторожность, когда термин встречается в литературе, поскольку сильное произведение используется и для обозначения тензорного произведения^[4].

См. также

• Произведение графов
• Прямое произведение графов
• Тензорное произведение графов

Примечания

1. Imrich, Klavžar, Rall, 2008.
2. Sabidussi, 1960, с. 446–457.
3. Berend, Korach, Zucker, 2005, с. 335–341.
4. Lovász, 1979, с. 2.

Литература

• Wilfried Imrich, Sandi Klavžar, Douglas F. Rall. Graphs and their Cartesian Product. — A. K. Peters, 2008. — ISBN 1-56881-429-1.
• Sabidussi, G. Graph multiplication // Math. Z.. — 1960. — Т. 72. — С. 446–457. — doi:10.1007/BF01162967.
• Daniel Berend, Ephraim Korach, Shira Zucker. Two-anticoloring of planar and related graphs // 2005 International Conference on Analysis of Algorithms. — Nancy: Association for Discrete Mathematics & Theoretical Computer Science, 2005. — С. 335–341. — (Discrete Mathematics & Theoretical Computer Science Proceedings).
• László Lovász. On the Shannon Capacity of a Graph // IEEE Transactions on Information Theory. — 1979. — Т. IT-25, вып. 1. — doi:10.1109/TIT.1979.1055985.