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

• Определение тензорного произведения

  • Тензорное произведение G × H двух графов G и H — это граф, вершины которого являются декартовым произведением V(G) × V(H), а смежные ребра соответствуют смежным ребрам в G и H. 
  • Тензорное произведение также известно как прямое произведение, продукт Кронекера, категориальный продукт, кардинальный продукт, реляционное произведение, слабое прямое произведение или конъюнкция. 

• Исторический контекст

  • Тензорное произведение введено Альфредом Нортом Уайтхедом и Бертраном Расселом в «Математических принципах» (1912). 
  • Оно эквивалентно произведению Кронекера матриц смежности графов. 

• Символика и примеры

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

• Свойства тензорного произведения

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

• Гипотеза и опровержение

  • Гипотеза Хедетниеми о хроматическом числе тензорного произведения была опровергнута Ярославом Шитовым. 

• Рекомендации и форматирование

  • Статья содержит рекомендации по форматированию и библиографическому описанию. 
  • Ссылки на внешние источники также включены в статью.