WikiSort.ru - Не сортированное

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

См. также

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

Примечания

Литература

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.