Введение
В теории графов тензорное произведение G × H графов G и H – это граф, у которого множество вершин G × H является декартовым произведением V(G) × V(H); и вершины (g, h) и (g', h') смежны в G × H тогда и только тогда, когда g смежен с g' в G, а h смежен с h' в H.
In graph theory, the tensor product G × H of graphs G and H is a graph such that
the vertex set of G × H is the Cartesian product V(G) × V(H); and
vertices (g,h) and math|(''g,h' ) are adjacent in G × H if and only if
g is adjacent to g' in G, andh is adjacent to h' in H.
The tensor product is also called the direct product, Kronecker product, categorical product, cardinal product, relational product, weak direct product, or conjunction'''. As an operation on binary relations, the tensor product was introduced by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica (1912). It is also equivalent to the Kronecker product of the adjacency matrices of the graphs. The notation G × H is also (and formerly normally was) used to represent another construction known as the Cartesian product of graphs, but nowadays more commonly refers to the tensor product. The cross symbol shows visually the two edges resulting from the tensor product of two edges. This product should not be confused with the strong product of graphs.
Тензорное произведение также называют прямым произведением, произведением Кронекера, категориальным произведением, кардинальным произведением, реляционным произведением, слабым прямым произведением или конъюнкцией. Как операция над бинарными отношениями, тензорное произведение было введено Альфредом Нортом Уайтхедом и Бертраном Расселом в их работе Principia Mathematica (1912). Оно также эквивалентно произведению Кронекера матриц смежности графов. Обозначение G × H также (и ранее обычно использовалось) для представления другой конструкции, известной как декартовое произведение графов, но в настоящее время чаще относится к тензорному произведению. Символ креста визуально отображает два ребра, возникающие в результате тензорного произведения двух ребер. Этот продукт не следует путать с сильным произведением графов.
In graph theory, the tensor product G × H of graphs G and H is a graph such that
the vertex set of G × H is the Cartesian product V(G) × V(H); and
vertices (g,h) and math|(''g,h' ) are adjacent in G × H if and only if
g is adjacent to g' in G, andh is adjacent to h' in H.
The tensor product is also called the direct product, Kronecker product, categorical product, cardinal product, relational product, weak direct product, or conjunction'''. As an operation on binary relations, the tensor product was introduced by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica (1912). It is also equivalent to the Kronecker product of the adjacency matrices of the graphs. The notation G × H is also (and formerly normally was) used to represent another construction known as the Cartesian product of graphs, but nowadays more commonly refers to the tensor product. The cross symbol shows visually the two edges resulting from the tensor product of two edges. This product should not be confused with the strong product of graphs.
Примеры
Тензорное произведение G × K2 представляет собой двудольный граф, называемый двудольным двойным покрытием графа G. Двудольным двойным покрытием графа Петерсена является граф Дезарга: K2 × G(5,2) = G(10,3). Двудольное двойное покрытие полного графа Kn является кроновым графом (полный двудольный граф Kn,n минус совершенное паросочетание). Тензорное произведение полного графа с самим собой является дополнением графа ладьи. Его вершины можно расположить в сетке, так что каждая вершина смежна с вершинами, которые не находятся в одной строке или столбце сетки.