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

Сильное произведение ${\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].