Тензорное произведение графов

Текущая версия страницы пока не проверялась опытными участниками и может значительно отличаться от , проверенной 20 октября 2020; проверки требуют .

Тензорное произведение называют также прямым произведением, категорийным произведением, реляционным произведением, произведением Кронекера, слабым прямым произведением или конъюнкцией. Альфред Норт Уайтхед и Бертран Рассел в книге Principia Mathematica[1] ввели тензорное произведение в виде операции бинарного отношения. Тензорное произведение графов также эквивалентно произведению Кронекера матриц смежности этих графов[2].

Если граф может быть представлен как тензорное произведение, то представление может быть не единственным, но каждое представление имеет одинаковое число неприводимых множителей. Вильфрид Имрих[4] привёл алгоритм полиномиального времени для распознавания тензорного произведения графов и нахождения разложения любого такого графа.

Гипотеза Хедетниеми даёт формулу для хроматического числа тензорного произведения.