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

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

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

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

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

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

Примеры

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

Свойства

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

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

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

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

${\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}}~,$

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

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

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

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

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

См. также

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

Ссылки

• Nicolas Bray. Graph Categorical Product (англ.) на сайте Wolfram MathWorld.