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

Тензорное произведение ${\displaystyle G\times H}$ графов ${\displaystyle G}$ и ${\displaystyle H}$ — граф, множество вершин которого есть декартово произведение ${\displaystyle V(G)\times V(H)}$, причём различные вершины ${\displaystyle (u,u')}$ и ${\displaystyle (v,v')}$ смежны в ${\displaystyle G\times H}$ тогда и только тогда, когда ${\displaystyle u}$ смежна с ${\displaystyle v}$ и ${\displaystyle u'}$ смежна с ${\displaystyle v'}$.

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

Другие названия

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

Обозначение ${\displaystyle G\times H}$ иногда используется для обозначения другой конструкции, известной как прямое произведение графов, но чаще обозначает тензорное произведение. Символ крестика показывает визуально два ребра, получающихся из тензорного произведения двух рёбер^[3]. Это произведение не следует путать с сильным произведением графов.

Примеры

• Тензорное произведение ${\displaystyle G\times K_{2}}$ является двудольным графом, который называется двойным покрытием двудольным графом графа ${\displaystyle G}$. Двойным покрытием двудольным графом графа Петерсена является граф Дезарга ${\displaystyle K_{2}\times G(5,2)=G(10,3)}$. Двойным покрытием двудольным графом полного графа ${\displaystyle K_{n}}$ является корона — полный двудольный граф ${\displaystyle K_{n,n}}$ без совершенного паросочетания).
• Тензорное произведение полного графа на себя является дополнением ладейного графа. Его вершины могут быть помещены в квадратную решётку ${\displaystyle n\times n}$ так, что каждая вершина смежна всем вершинам, не лежащим в тех же строке или столбце.

Свойства

Тензорное произведение является категорийно-теоретическим произведением в категории графов и гомоморфизмов, то есть гомоморфизм в ${\displaystyle G\times H}$ соответствует паре гомоморфизмов в ${\displaystyle G}$ и в ${\displaystyle H}$. В частности, граф ${\displaystyle I}$ допускает гомоморфизм в ${\displaystyle G\times H}$ тогда и только тогда, когда он допускает гомоморфизм в оба множителя.

С одной стороны, пара гомоморфизмов ${\displaystyle f_{G}:I\to G}$ и ${\displaystyle f_{H}:I\to H}$ дают гомоморфизм:

${\displaystyle {\begin{cases}f:I\to G\times H\\f(v)=\left(f_{G}(v),f_{H}(v)\right)\end{cases}}~,}$

с другой, гомоморфизм ${\displaystyle f\colon I\to G\times H}$ может быть применён к гомоморфизмам проекций:

${\displaystyle {\begin{cases}\pi _{G}:G\times H\to G\\\pi _{G}((u,u'))=u\end{cases}}\qquad \qquad {\begin{cases}\pi _{H}:G\times H\to H\\\pi _{G}((u,u'))=u'\end{cases}}~,}$

давая тем самым гомоморфизмы в ${\displaystyle G}$ и в ${\displaystyle H}$.

Матрица смежности графа ${\displaystyle G\times H}$ является тензорным произведением матриц смежности ${\displaystyle G}$ и ${\displaystyle H}$.

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

Если либо ${\displaystyle G}$, либо ${\displaystyle H}$ является двудольным, то является двудольным и их тензорное произведение. Граф ${\displaystyle G\times H}$ связен тогда и только тогда, когда оба множителя связаны и, по меньшей мере, один множитель не является двудольным^[5]. В частности, двойное покрытие двудольным графом графа ${\displaystyle G}$ связно тогда и только тогда, когда ${\displaystyle G}$ связен и не двудолен.

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

См. также

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