В теории графов тензорное произведение G × H графов G и H — это граф, такой что
Тензорное произведение также называется прямым произведением , произведением Кронекера , категориальным произведением , кардинальным произведением , реляционным произведением , слабым прямым произведением или конъюнкцией . Как операция над бинарными отношениями, тензорное произведение было введено Альфредом Нортом Уайтхедом и Бертраном Расселом в их Principia Mathematica (1912). Оно также эквивалентно произведению Кронекера матриц смежности графов. [1]
Обозначение G × H также (и раньше обычно использовалось) для представления другой конструкции, известной как декартово произведение графов , но в настоящее время чаще относится к тензорному произведению. Символ креста визуально показывает два ребра, полученные из тензорного произведения двух ребер. [2] Это произведение не следует путать с сильным произведением графов .
Тензорное произведение — это теоретико-категорное произведение в категории графов и гомоморфизмов графов . То есть гомоморфизм в G × H соответствует паре гомоморфизмов в G и в H. В частности, граф I допускает гомоморфизм в G × H тогда и только тогда , когда он допускает гомоморфизм в G и в H.
Чтобы увидеть это, в одном направлении заметим, что пара гомоморфизмов f G : I → G и f H : I → H дает гомоморфизм
В другом направлении гомоморфизм f : I → G × H может быть составлен с проекциями гомоморфизмов
чтобы получить гомоморфизмы к G и к H.
Матрица смежности G × H является произведением Кронекера ( тензором ) матриц смежности G и H.
Если граф можно представить как тензорное произведение, то может быть несколько различных представлений (тензорные произведения не удовлетворяют уникальной факторизации), но каждое представление имеет одинаковое количество неприводимых множителей. Имрих (1998) дает полиномиальный алгоритм времени для распознавания графов тензорных произведений и нахождения факторизации любого такого графа.
Если G или H являются двудольными , то их тензорное произведение также является связным. G × H связно тогда и только тогда, когда оба фактора связны и по крайней мере один фактор недвудольный. [3] В частности, двудольное двойное покрытие G связно тогда и только тогда, когда G связно и недвудольно.
Гипотеза Хедетниеми , давшая формулу для хроматического числа тензорного произведения, была опровергнута Ярославом Шитовым (2019).
Тензорное произведение графов снабжает категорию графов и гомоморфизмов графов структурой симметричной замкнутой моноидальной категории . Пусть G 0 обозначает базовое множество вершин графа G . Внутренний hom [ G , H ] имеет функции f : G 0 → H 0 в качестве вершин и ребро из f : G 0 → H 0 в f' : G 0 → H 0 всякий раз, когда ребро { x , y } в G влечет { f ( x ), f ' ( y )} в H . [4]
