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

редактировать
Тензорное произведение графов.

В теории графов тензорное произведение G × H графов G и H является графом, таким что

  • множество вершин графа G × H является декартовым продукт V (G) × V (H); и
  • вершины (g, h) и (g ', h') смежны в G × H тогда и только тогда, когда
    • g смежно с g '
    • h смежно с h '.

Тензорное произведение также называется прямым произведением, произведением Кронекера, категориальным произведением, кардинальным произведением, реляционный продукт, слабый прямой продукт или соединение . В качестве операции над бинарными отношениями тензорное произведение было введено Альфредом Норт Уайтхедом и Бертраном Расселом в их Principia Mathematica (1912). Он также эквивалентен произведению Кронекера матриц смежности графов.

Обозначение G × H также (и раньше обычно использовалось) используется для представления другая конструкция, известная как декартово произведение графов, но в настоящее время чаще относится к тензорному произведению. Символ креста визуально показывает два ребра, полученные в результате тензорного произведения двух ребер. Этот продукт не следует путать с сильным продуктом графиков.

Содержание

  • 1 Примеры
  • 2 Свойства
  • 3 См. Также
  • 4 Примечания
  • 5 Ссылки
  • 6 Внешние links

Примеры

Свойства

Тензорное произведение - это теоретико-категориальный продукт в категории графов и гомоморфизмы графов. То есть гомоморфизм в G × H соответствует паре гомоморфизмов в G и H. В частности, граф I допускает гомоморфизм в G × H тогда и только тогда, когда он допускает гомоморфизм в G и в H.

Чтобы увидеть это в одном направлении, заметим, что пара гомоморфизмов f G : I → G и f H : I → H порождает гомоморфизм

{f: I → G × H f (v) = (f G (v), f H (v)) {\ displaystyle {\ begin {cases} f: I \ to G \ times ЧАС\\ f (v) = \ left (f_ {G} (v), f_ {H} (v) \ right) \ end {cases}}}{ \ Displaystyle {\ begin {case} f: I \ to G \ times H \\ f (v) = \ left (f_ {G} (v), f_ {H} (v) \ right) \ end {cases} }}

В обратном направлении гомоморфизм f: I → G × H можно составить с гомоморфизмами проекций

{π G: G × H → G π G ((u, u ′)) = u {π H: G × H → H π H ((u, u ′)) знак равно U ′ {\ Displaystyle {\ begin {cases} \ pi _ {G}: G \ times H \ to G \\\ pi _ {G} ((u, u ')) = u \ end {cases}} \ qquad \ qquad {\ begin {cases} \ pi _ {H}: G \ times H \ to H \\\ pi _ {H} ((u, u ')) = u' \ end {cases}}}{\displaystyle {\begin{cases}\pi _{G}:G\times H\to G\\\pi _{G}((u,u'))=u\end{cases}}\qquad \qquad {\begin{cases}\pi _{H}:G\times H\to H\\\pi _{H}((u,u'))=u'\end{cases}}}

для получения гомоморфизмов G и H.

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

Если граф можно представить как тензорное произведение, тогда может быть несколько различных представлений (тензорные произведения не удовлетворяют уникальной факторизации), но каждое представление имеет одинаковое количество неприводимых факторов. Имрих (1998) дает алгоритм полиномиального времени для распознавания тензорных графов произведения и нахождения факторизации любого такого графа.

Если либо G, либо H двудольные, то их тензорное произведение также. G × H связно тогда и только тогда, когда оба фактора связаны и хотя бы один фактор не является двудольным. В частности, двудольное двойное покрытие группы G связно тогда и только тогда, когда G связна и недвольна.

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

Тензорное произведение графов наделяет категорию графов и гомоморфизмов графов структурой симметричной замкнутой моноидальной категории. Пусть G 0 {\ displaystyle G_ {0}}G_ {0} обозначает базовый набор вершин графа G {\ displaystyle G}G . Внутренний hom [G, H] {\ displaystyle [G, H]}{\ displaystyle [G, H]} имеет функции f: G 0 → H 0 {\ displaystyle f: G_ {0} \ to H_ {0}}{\ displaystyle f: G_ {0} \ to H_ {0}} как вершины и ребро от f: G 0 → H 0 {\ displaystyle f: G_ {0} \ до H_ {0}}{\ displaystyle f: G_ {0} \ to H_ {0}} до f ′: G 0 → H 0 {\ displaystyle f ': G_ {0} \ to H_ {0}}{\displaystyle f':G_{0}\to H_{0}}всякий раз, когда край {x, y} {\ displaystyle \ {x, y \}}\ {x, y \} в G {\ displaystyle G}G подразумевает {f (x), f ′ (y)} {\ displaystyle \ {f ( x), f '(y) \}}{\displaystyle \{f(x),f'(y)\}}в H {\ displaystyle H}H .

См. также

Примечания

Список литературы

Внешние ссылки

Последняя правка сделана 2021-06-10 13:37:48
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте