그래프의 텐서 곱

그래프 이론에서 그래프 G와 H의 텐서 곱 G × H는 다음과 같은 그래프다.

• G × H의 정점 세트는 데카르트 제품 V(G) × V(H)이다.
• 정점(g,h) 및 (g',h')은 다음과 같은 경우에만 G × H에 인접한다.
  • g는 g'에 인접하며,
  • h는 h'에 인접해 있다.

텐서 제품은 다이렉트 제품, 크론커 제품, 범주형 제품, 기본 제품, 관계형 제품, 약한 다이렉트 제품 또는 접속사라고도 불린다. 이항 관계에 대한 수술로서 텐서 제품은 알프레드 노스 화이트헤드와 버트랜드 러셀에 의해 그들의 프린세스 매머티카(1912년)에 소개되었다. 이것은 또한 그래프의 인접 행렬의 크론커 제품과 동등하다.^[1]

G × H라는 표기법도 그래프의 데카르트 산물이라고 알려진 또 다른 구조를 나타내기 위해 사용되었지만, 오늘날에는 더 흔히 텐서 산물을 가리킨다. 십자 기호는 두 가장자리의 텐서 제품에서 발생하는 두 가장자리를 시각적으로 보여준다.^[2] 이 제품은 그래프의 강한 제품과 혼동해서는 안 된다.

예

• 텐서 제품 G × K는₂ G의 초당적 이중 커버라고 불리는 초당적 그래프다. 피터슨 그래프의 초당적 이중 표지는 데스투게스 그래프: K₂ × G(5,2) = G(10,3)이다. 전체 그래프 K의_n 초당적 이중 커버는 크라운 그래프(완전한 초당적 그래프 K에서_n,n 완벽한 매칭을 뺀 것)이다.
• 그 자체로 완성된 그래프의 텐서 제품은 룩의 그래프를 보완한 것이다. 그것의 꼭지점은 n by n 그리드에 위치할 수 있다. 그래서 각 꼭지점은 그리드의 같은 행이나 열에 있지 않은 꼭지점에 인접한다.

특성.

텐서(tensor) 제품은 그래프와 그래프 동형성의 범주에서 범주의 기형적인 제품이다. 즉, G × H에 대한 동형성은 G와 H에 대한 동형성의 한 쌍에 해당한다. 특히 G와 H로 동형성을 인정하는 경우에만 G × H로 동형성을 인정하는 그래프.

그것을 보기 위해서, 한 방향으로, 한 쌍의 동형성 f_G : I → G, f : I_H → H가 동형성을 산출하는 것을 관찰한다.

${\displaystyle {\reason{case}f:I\to G\time H\\f(v)=\왼쪽(f_{G}(v),f_{H}(v)\오른쪽)\case}}}}$

다른 방향에서는 동형성 f: I → G × H를 투영 동형성으로 구성할 수 있다.

${\displaystyle {\begin}\pi _{G:G\to G\\\pi _{G}(u,u')=u\end{case}\qquad \qquad \begin}\pi _{H:G\time H\to H\\\pi _{H}(우,u')=u'\end{case}}}$

G와 H에 동형성을 부여한다.

G × H의 인접 행렬은 G와 H의 인접 행렬의 크론커(텐서) 제품이다.

그래프를 텐서 제품으로 나타낼 수 있는 경우 여러 가지 다른 표현(텐서 제품이 고유한 요인화를 만족하지 않음)이 있을 수 있지만 각 표현은 같은 수의 수정 불가능한 요소를 가지고 있다. Imrich(1998)는 텐서 제품 그래프를 인식하고 그러한 그래프의 인자화를 찾기 위한 다항 시간 알고리즘을 제공한다.

만약 G나 H가 초당적인 것이라면, 그들의 텐서 제품도 그렇다. G × H는 두 인자가 모두 연결되어 있고 적어도 한 인자가 비바타이트인 경우에만 연결된다.^[3] 특히 G의 초당적 이중 커버는 G가 연결되어 있지 않은 경우에만 연결된다.

텐서 제품의 색수를 공식화한 헤데니에미 추측은 야로슬라프 시토프(2019년)가 반증했다.

그래프의 텐서적 산물은 그래프의 범주와 그래프 동형성을 대칭으로 닫힌 단일형 범주의 구조와 함께 장착한다. Let $G{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$은(는$)$ 그래프 G {\$displaystyle G}$의 기본 정점 집합을 나타낸다$$$.$ 내부 hom${\displaystyle }$[${\displaystyle G,}$ H ${\displaystyle ]}$ ${\displaystyle [G,$${\displaystyle {H\mathrm{}}_{}}$$]}$은(는) 함수 $f{\displaystyle }$: ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$→ H ${\$ f$:$$G_${${\displaystyle {0\mathrm{}}_{}}$$}\to H_{0}$ 정점 및 f${\displaystyle }$: G ${\displaystyle {0\mathrm{}}_{}{}_{}}$→ H ${\$$G_{0}\to H_{0}$에서 f${\displaystyle {}^{}}f{\displaystyle {}^{}}$: ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$→ ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$ f$':$$G{\displaystyle }$ ${\displaystyle G}$의 에지${\displaystyle }${${\displaystyle x\},}$ $},$ {$x,y\}$이(가)가${\displaystyle }${$x),$을(를) 의미할 때마다$$ $G_{0}\$$displaystyle$ H$}$의$$^[4]에지$$ {f($x),f(y)\}$를 의미함$.$

참고 항목

• 그래프 제품
• 그래프의 강력한 산물

메모들

참조

• Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. (2008), "Graphs of Morphisms of Graphs", The Electronic Journal of Combinatorics, 15: A1.
• Hahn, Geňa; Sabidussi, Gert (1997), Graph symmetry: algebraic methods and applications, NATO Advanced Science Institutes Series, vol. 497, Springer, p. 116, ISBN 978-0-7923-4668-5.
• Imrich, W. (1998), "Factoring cardinal product graphs in polynomial time", Discrete Mathematics, 192: 119–144, doi:10.1016/S0012-365X(98)00069-7, MR 1656730
• Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8
• Shitov, Yaroslav (May 2019), Counterexamples to Hedetniemi's conjecture, arXiv:1905.02167
• Weichsel, Paul M. (1962), "The Kronecker product of graphs", Proceedings of the American Mathematical Society, 13 (1): 47–52, doi:10.2307/2033769, JSTOR 2033769, MR 0133816
• Whitehead, A. N.; Russell, B. (1912), Principia Mathematica, Cambridge University Press, vol. 2, p. 384

외부 링크

• Nicolas Bray. "Graph Categorical Product". MathWorld.