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

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

См. также

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