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

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

Тензорное произведение ${\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}$ связен и не двудолен.

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

См. также

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

Примечания

1. Whitehead, Russell, 1912.
2. Weichsel, 1962.
3. Hahn, Sabidussi, 1997.
4. Imrich, 1998.
5. Imrich, Klavžar, 2000, с. Theorem 5.29.

Литература

• Geňa Hahn, Gert Sabidussi. Graph symmetry: algebraic methods and applications. — Springer, 1997. — Т. 497. — С. 116. — (NATO Advanced Science Institutes Series). — ISBN 978-0-7923-4668-5.
• Imrich W. Factoring cardinal product graphs in polynomial time // Discrete Mathematics. — 1998. — Т. 192. — С. 119–144. — doi:10.1016/S0012-365X(98)00069-7.
• Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8.
• Paul M. Weichsel. The Kronecker product of graphs // Proceedings of the American Mathematical Society. — 1962. — Т. 13, вып. 1. — С. 47–52. — doi:10.2307/2033769. — JSTOR 2033769.
• Whitehead A. N., Russell B. Principia Mathematica. — Cambridge University Press, 1912.

Ссылки

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