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

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

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

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

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

Примеры

Тензорное произведение $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$ .

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

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

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

См. также

Примечания

↑ Whitehead, Russell, 1912.
↑ Weichsel, 1962.
↑ Hahn, Sabidussi, 1997.
↑ Imrich, 1998.
↑ 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.

[_bab230da4b3e0635-1] Whitehead, Russell, 1912.

[_8acf08969b70f153-2] Weichsel, 1962.

[_38bbf300fba2b0f5-3] Hahn, Sabidussi, 1997.

[_1e895058bf14da58-4] Imrich, 1998.

[_574595cad1a23b31-5] Imrich, Klavžar, 2000, с. Theorem 5.29.

[1]

[2]

[3]

[4]

[5]