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

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

Сильное произведение $G\boxtimes H$ графов G и H — это граф, такой что

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

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

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

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

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

См. также

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