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

В теории графов тензорное произведение $G \times H$ графов $G$ и $H$ — это граф такой, что

множество вершин G $\times$ $H$ — это декартово произведение $V$ $($ $G$ $) \times$ $V$ $($ $H$ $)$ $;$ и
вершины ( g , h ) и ( g' , h' ) смежны в G × H тогда и только тогда, когда
- $g$ смежно с g $'$ в $G$ и
- $h$ смежно с $h'$ в $H$ .

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

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

Примеры

Тензорное произведение $G \times K 2$ представляет собой двудольный граф , называемый двудольным двойным покрытием $G.$ Двудольное двойное покрытие графа Петерсена — это граф Дезарга : $K 2 \times G (5,2) = G (10,3)$ . Двудольное двудольное покрытие полного графа $Kn$ является графом $-$ короной ( полный $двудольный$ граф $Kn$ $,$ $n$ минус совершенное паросочетание ).
Тензорное произведение полного графа на самого себя является дополнением ладейного графа . Его вершины можно разместить в сетке размером $n$ × $n$ , так что каждая вершина примыкает к вершинам, которые не находятся в той же строке или столбце сетки.

Характеристики

Тензорное произведение — это теоретико-категорное произведение в категории графов и гомоморфизмов графов . То есть гомоморфизму $G \times H$ соответствует пара гомоморфизмов $G$ и $H$ . В частности, граф $I$ допускает гомоморфизм в $G \times H$ тогда и только тогда, когда он допускает гомоморфизм в $G$ и в $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 : 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 _{H}((u,u'))=u'\end{cases}}

чтобы получить гомоморфизмы в $G$ и в $H$ .

Матрица смежности $G \times H$ представляет собой кронекеровское (тензорное) произведение матриц смежности G $и$ H $.$

Если граф можно представить в виде тензорного произведения, то может существовать несколько разных представлений (тензорные произведения не удовлетворяют уникальной факторизации), но каждое представление имеет одинаковое количество неприводимых факторов. Имрих (1998) предлагает алгоритм с полиномиальным временем для распознавания графов тензорных произведений и нахождения факторизации любого такого графа.

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

Гипотезу Хедетниеми , давшую формулу хроматического числа тензорного произведения, опровергла Ярослав Шитов (2019).

Тензорное произведение графов придает категории графов и гомоморфизмов графов структуру симметричной замкнутой моноидальной категории . Пусть $G 0$ обозначает базовое множество вершин графа $G$ . Внутренний hom $[$ $G, H] имеет$ функции $f : G0 \to H0$ как вершины и ребро из $f$ $:$ $G0$ $\to$ $H0$ $в$ f $' :$ $G0$ $\to$ $H0$ $всякий раз$ $,$ когда ребро ${x, y}$ в $G$ влечет $за$ $собой$ ${$ $ж$ $($ $Икс$ $),$ $ж '$ $($ $у$ $)}$ в $ЧАС$ . ^[4]

Смотрите также

Примечания

^ Вайхзель 1962.
^ Хан и Сабидусси 1997.
^ Имрих и Клавжар 2000, Теорема 5.29.
^ Браун и др. 2008 г.; см. также это доказательство

Внешние ссылки