Тензорное произведение графов
-
Определение тензорного произведения
- Тензорное произведение G × H двух графов G и H — это граф, вершины которого являются декартовым произведением V(G) × V(H), а смежные ребра соответствуют смежным ребрам в G и H.
- Тензорное произведение также известно как прямое произведение, продукт Кронекера, категориальный продукт, кардинальный продукт, реляционное произведение, слабое прямое произведение или конъюнкция.
-
Исторический контекст
- Тензорное произведение введено Альфредом Нортом Уайтхедом и Бертраном Расселом в «Математических принципах» (1912).
- Оно эквивалентно произведению Кронекера матриц смежности графов.
-
Символика и примеры
- Тензорное произведение может быть представлено символом креста, который визуально отображает два ребра.
- Примеры включают двудольные двойные покрытия графов и коронные графы.
-
Свойства тензорного произведения
- Тензорное произведение является теоретико-категориальным произведением в категории графов и гомоморфизмов.
- Оно обладает структурой симметричной замкнутой моноидальной категории.
-
Гипотеза и опровержение
- Гипотеза Хедетниеми о хроматическом числе тензорного произведения была опровергнута Ярославом Шитовым.
-
Рекомендации и форматирование
- Статья содержит рекомендации по форматированию и библиографическому описанию.
- Ссылки на внешние источники также включены в статью.
Полный текст статьи: