Тензорний добуток графів

Тензорний добуток графів

Тензорний добуток $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^{*}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