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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Тензорное произведение графов.

Тензорное произведение графов и граф, множество вершин которого есть декартово произведение , причём различные вершины и смежны в тогда и только тогда, когда смежна с и смежна с .

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

[править | править код]

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

Обозначение иногда используется для обозначения другой конструкции, известной как прямое произведение графов, но чаще обозначает тензорное произведение. Символ крестика показывает визуально два ребра, получающихся из тензорного произведения двух рёбер[3]. Это произведение не следует путать с сильным произведением графов.

Тензорное произведение является категорийно-теоретическим произведением в категории графов и гомоморфизмов, то есть гомоморфизм в соответствует паре гомоморфизмов в и в . В частности, граф допускает гомоморфизм в тогда и только тогда, когда он допускает гомоморфизм в оба множителя.

С одной стороны, пара гомоморфизмов и дают гомоморфизм:

с другой, гомоморфизм может быть применён к гомоморфизмам проекций:

давая тем самым гомоморфизмы в и в .

Матрица смежности графа является тензорным произведением матриц смежности и .

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

Если либо , либо является двудольным, то является двудольным и их тензорное произведение. Граф связен тогда и только тогда, когда оба множителя связаны и, по меньшей мере, один множитель не является двудольным[5]. В частности, двойное покрытие двудольным графом графа связно тогда и только тогда, когда связен и не двудолен.

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

Примечания

[править | править код]

Литература

[править | править код]
  • 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. — JSTOR 2033769.
  • Whitehead A. N., Russell B. Principia Mathematica. — Cambridge University Press, 1912.