WikiSort.ru - Не сортированное

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

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

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

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

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

Примеры

• Тензорное произведение ${\displaystyle G\times K_{2}}$ является двудольным графом, который называется двойным покрытием двудольным графом графа G. Двойным покрытием двудольным графом графа Петерсена является граф Дезарга K₂ × G(5,2)=G(10,3). Двойным покрытием двудольным графом полного графа K_n является корона (полный двудольный граф K_n,n минус совершенное паросочетание).
• Тензорным произведением полного графа на себя является дополнением ладейного графа. Его вершины могут быть помещены в n-на-n решётку, так что каждая вершина смежна вершинам, которые не в той же строке или в том же столбце.

Свойства

Тензорное произведение является категорийно-теоретическим произведением в категории графов и гомоморфизмов. То есть гомоморфизм в ${\displaystyle G\times H}$ соответствует паре гомоморфизмов в G и в H. В частности, граф I допускает гомоморфизм в ${\displaystyle G\times H}$ тогда и только тогда, когда он допускает гомоморфизм в G и в H.

Чтобы увидеть это, в одном направлении, заметим, что пара гомоморфизмов ${\displaystyle f_{G}:I\to G}$ и ${\displaystyle f_{H}:I\to H}$ дают гомоморфизм

${\displaystyle {\begin{cases}f:I\to G\times H\\f(v)=\left(f_{G}(v),f_{H}(v)\right)\end{cases}}}$

В обратном направлении, гомоморфизм ${\displaystyle f\colon I\to G\times H}$ может быть применён к гомоморфизмам проекций

${\displaystyle {\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.

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

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

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

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

См. также

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

Примечания

Литература

Ссылки

• Nicolas Bray. Graph Categorical Product (англ.) на сайте Wolfram MathWorld.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. Проверить статью на грамматические и орфографические ошибки.