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

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

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

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

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

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

Примеры

• Тензорное произведение $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{array}{c}f:I\to G\times H\\ f(v)=(f_G(v),f_H(v))\end{array},$

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

$\{\begin{array}{c}{\pi }_G:G\times H\to G\\ {\pi }_G((u,u^{\prime }))=u\end{array}\{\begin{array}{c}{\pi }_H:G\times H\to H\\ {\pi }_G((u,u^{\prime }))=u^{\prime }\end{array},$

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

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

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

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

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

См. также

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

Литература

• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга

Ссылки

• Шаблон:Mathworld