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

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

множество вершин × $G V H$ — это декартово произведение $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)$ . Двудольное двудольное покрытие полного графа $является n$ графом -короной ( полный двудольный граф $Kn, . Kn$ минус совершенное паросочетание )
Тензорное произведение полного графа на самого себя является дополнением графа ладейного . Его вершины можно разместить в $n$ сетке размером $\times 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 год ; см. также это доказательство

Ссылки [ править ]

Браун, Р.; Моррис, И.; Шримптон, Дж.; Уэнсли, CD (2008), «Графики морфизмов графов», Электронный журнал комбинаторики , 15 : A1 .
Хан, Геня; Сабидусси, Герт (1997), Симметрия графа: алгебраические методы и приложения , Серия институтов передовых научных исследований НАТО, том. 497, Спрингер, с. 116, ISBN 978-0-7923-4668-5 .
Имрич, В. (1998), «Факторизация графиков кардинальных произведений за полиномиальное время», Discrete Mathematics , 192 : 119–144, doi : 10.1016/S0012-365X(98)00069-7 , MR 1656730
Имрих, Вильфрид; Клавжар, Сэнди (2000), Графики продуктов: структура и распознавание , Wiley, ISBN 0-471-37039-8
Шитов, Ярослав (май 2019 г.), Контрпримеры к гипотезе Хедетниеми , arXiv : 1905.02167
Вайхзель, Пол М. (1962), «Произведение графов Кронекера», Труды Американского математического общества , 13 (1): 47–52, doi : 10.2307/2033769 , JSTOR 2033769 , MR 0133816
Уайтхед, АН ; Рассел, Б. (1912), Principia Mathematica , Cambridge University Press, vol. 2, с. 384

Внешние ссылки [ править ]

Николас Брэй. «График категориального произведения» . Математический мир .

[FOOTNOTEWeichsel1962-1] Висла 1962 .

[FOOTNOTEHahnSabidussi1997-2] Хан и Сабидусси 1997 .

[3] Имрих и Клавжар 2000 , Теорема 5.29.

[FOOTNOTEBrownMorrisShrimptonWensley2008-4] Браун и др. 2008 год ; см. также это доказательство

[1]

[2]

[3]

[4]

v т и Альфред Норт Уайтхед
Книги	Принципы математики (1910–1913) глоссарий Процесс и реальность (1929)
Концепции	Инертные знания Бесточечная геометрия Философия процесса Тензорное произведение графов Теория гравитации
Изучать	Центр исследований процессов Современные исследования Уайтхеда Исследовательский проект Уайтхеда