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

Сильное произведение $G ⊠ H$ графов G и H — это граф, такой, чтоШаблон:Sfn:

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

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

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

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

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