Тензорний добуток графів

математична операція в теорії графів

Тензорний добуток графів і  — граф, множина вершин якого є декартовим добутком , причому різні вершини і суміжні в тоді, коли суміжна з і суміжна з .

Тензорний добуток графів

Інші назвиРедагувати

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

Позначення   іноді використовується для позначення іншої конструкції, відомої як прямий добуток графів, але частіше позначає тензорний добуток. Символ хрестика показує візуально два ребра, що виходять з тензорного добутку двох ребер[3]. Цей добуток не слід плутати зі сильним добутком графів.

ПрикладиРедагувати

ВластивостіРедагувати

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

З одного боку, пара гомоморфізмів   і   дають гомоморфізм:

 

з іншого, гомоморфізм   можна застосувати до гомоморфізму проєкцій:

 

даючи тим самим гомоморфізми в   і в  .

Матриця суміжності графу   є тензорним добутком матриць суміжності   і  .

Якщо граф можна подати як тензорний добуток, то подання може бути не єдиним, але кожне подання має однакове число незвідних множників. Вільфрід Імріх[4] навів алгоритм поліноміального часу для розпізнавання тензорного добутку графів і знаходження розкладу будь-якого такого графу.

якщо або  , або   є двочастковим, то є двочастковим і їх тензорний добуток. Граф   зв'язний тоді і тільки тоді, коли обидва множники пов'язані і, щонайменше, один множник не є дводольним[5]. Зокрема, подвійне покриття дводольним графом графу   зв'язне тоді і тільки тоді, коли   зв'язний і не двочастковий.

Гіпотеза Гедетніємі дає формулу для хроматичного числа тензорного добутку.

Див. такожРедагувати

ПриміткиРедагувати

ЛітератураРедагувати

ПосиланняРедагувати