Тензорное произведение графов
Тензорное произведение графов и — граф, множество вершин которого есть декартово произведение , причём различные вершины и смежны в тогда и только тогда, когда смежна с и смежна с .
Другие названия
Тензорное произведение называют также прямым произведением, категорийным произведением, реляционным произведением, произведением Кронекера, слабым прямым произведением или конъюнкцией. Альфред Норт Уайтхед и Бертран Рассел в книге Principia Mathematica[1] ввели тензорное произведение в виде операции бинарного отношения. Тензорное произведение графов также эквивалентно произведению Кронекера матриц смежности этих графов[2].
Обозначение иногда используется для обозначения другой конструкции, известной как прямое произведение графов, но чаще обозначает тензорное произведение. Символ крестика показывает визуально два ребра, получающихся из тензорного произведения двух рёбер[3]. Это произведение не следует путать с сильным произведением графов.
Примеры
- Тензорное произведение является двудольным графом, который называется двойным покрытием двудольным графом графа . Двойным покрытием двудольным графом графа Петерсена является граф Дезарга . Двойным покрытием двудольным графом полного графа является корона — полный двудольный граф без совершенного паросочетания).
- Тензорное произведение полного графа на себя является дополнением ладейного графа. Его вершины могут быть помещены в квадратную решётку так, что каждая вершина смежна всем вершинам, не лежащим в тех же строке или столбце.
Свойства
Тензорное произведение является категорийно-теоретическим произведением в категории графов и гомоморфизмов, то есть гомоморфизм в соответствует паре гомоморфизмов в и в . В частности, граф допускает гомоморфизм в тогда и только тогда, когда он допускает гомоморфизм в оба множителя.
С одной стороны, пара гомоморфизмов и дают гомоморфизм:
с другой, гомоморфизм может быть применён к гомоморфизмам проекций:
давая тем самым гомоморфизмы в и в .
Матрица смежности графа является тензорным произведением матриц смежности и .
Если граф может быть представлен как тензорное произведение, то представление может быть не единственным, но каждое представление имеет одинаковое число неприводимых множителей. Вильфрид Имрих[4] привёл алгоритм полиномиального времени для распознавания тензорного произведения графов и нахождения разложения любого такого графа.
Если либо , либо является двудольным, то является двудольным и их тензорное произведение. Граф связен тогда и только тогда, когда оба множителя связаны и, по меньшей мере, один множитель не является двудольным[5]. В частности, двойное покрытие двудольным графом графа связно тогда и только тогда, когда связен и не двудолен.
Гипотеза Хедетниеми даёт формулу для хроматического числа тензорного произведения.
См. также
Примечания
- ↑ Whitehead, Russell, 1912.
- ↑ Weichsel, 1962.
- ↑ Hahn, Sabidussi, 1997.
- ↑ Imrich, 1998.
- ↑ Imrich, Klavžar, 2000, с. Theorem 5.29.
Литература
- Geňa Hahn, Gert Sabidussi. Graph symmetry: algebraic methods and applications. — Springer, 1997. — Т. 497. — С. 116. — (NATO Advanced Science Institutes Series). — ISBN 978-0-7923-4668-5.
- Imrich W. Factoring cardinal product graphs in polynomial time // Discrete Mathematics. — 1998. — Т. 192. — С. 119–144. — doi:10.1016/S0012-365X(98)00069-7.
- Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8.
- Paul M. Weichsel. The Kronecker product of graphs // Proceedings of the American Mathematical Society. — 1962. — Т. 13, вып. 1. — С. 47–52. — doi:10.2307/2033769. — .
- Whitehead A. N., Russell B. Principia Mathematica. — Cambridge University Press, 1912.
Ссылки
- Nicolas Bray. Graph Categorical Product (англ.) на сайте Wolfram MathWorld.