데카르트 산물 그래프

그래프 이론에서 그래프 G와 H의 데카르트 제품 G□H는 다음과 같은 그래프 입니다.

• G□H의 꼭지점 세트는 데카르트 제품 V(G) × V(H)이다.
• 두 꼭지점(u,u' )과 (v,v' )은 다음 중 하나에 해당하는 경우에만 G□H에 인접해 있다.
  • u = v 및 u'는 H의 v'에 인접하거나
  • u' = v'와 u는 g의 v에 인접해 있다.

데카르트 산물의 그래프는 때때로 그래프의 상자 산물이라고 불린다[Harary 1969].

그래프(F□G)□H 및 F□(G□H)는 자연적으로 이형성이므로 연산은 연관성이 있다. 이 연산은 그래프의 이형성 등급에 대한 연산으로, 더 강하게 그래프 G□H와 H□G는 자연적으로 이형성이지만, 라벨링된 그래프에 대한 연산으로 연산은 조합되지 않는다.

표기법 G × H는 종종 그래프의 카르테시안 제품에 사용되었지만, 지금은 그래프의 텐서 제품으로 알려진 또 다른 구조에 더 일반적으로 사용된다. 사각형 기호는 두 모서리의 데카르트 제품에서 발생하는 네 모서리를 시각적으로 보여주기 때문에 데카르트 제품을 위한 직관적이고 모호하지 않은 표기법이다.^[1]

예

• 두 개의 가장자리가 있는 데카르트 제품은 네 개의 꼭지점에 있는 사이클이다. K₂□K₂ = C₄.
• K의₂ 데카르트 제품과 경로 그래프는 사다리 그래프다.
• 두 개의 경로 그래프의 데카르트 산물은 격자 그래프다.
• 가장자리가 n개인 데카르트 제품은 하이퍼큐브:

${\displaystyle (K_{2})^{\square n}=Q_{n}.}$

따라서 두 개의 하이퍼큐브 그래프의 데카르트 산물은 또 다른 하이퍼큐브다. Q_i□Q_j = Q_i+j.

• 두 개의 중위수 그래프의 데카르트 산물은 또 다른 중위수 그래프다.
• n-prism의 정점과 가장자리 그래프는 데카르트 제품 그래프 K₂□C이다_n.
• 루크의 그래프는 두 개의 완전한 그래프로 이루어진 데카르트 제품이다.

특성.

연결된 그래프가 데카르트 제품일 경우, 주요 인자의 산물로서, 그래프의 산물로 분해될 수 없는 그래프를 고유하게 인수할 수 있다.^[2] 그러나 Imrich & Klavzar(2000년)는 두 가지 다른 방식으로 표현할 수 있는 분리된 그래프를 프라임 그래프의 데카르트 제품이라고 설명한다.

(K₁ + K₂ + K₂²)□(K₁ + K₂³) = (K₁ + K₂² + K₂⁴)□(K₁ + K₂),

여기서 더하기 기호는 결합을 해제하고 위첨자는 데카르트 제품에 대한 강조를 나타낸다.

데카르트 제품은 각각의 요인이 있는 경우에만 정점 전이성 제품이다.^[3]

카르테시안 제품은 각각의 요인이 있는 경우에만 초당적이다. 보다 일반적으로, 데카르트 제품의 색수는 방정식을 만족시킨다.

χ(G□H) = 최대 { {(G), χ(H)}.^[4]

Hedetniemi 추측에 따르면 그래프의 텐서 곱에 관련된 동일성이 있다. 데카르트 제품의 독립번호는 그렇게 쉽게 계산되지 않지만, Vizing(1963)이 보여주듯이 불평등을 만족시킨다.

α(G)α(H) + min{ V(G) -α(G), V(H) -α(H)} α(G□H) ≤min{α(G) V(G) ≤.

Vizing 추측에 따르면 카르테시안 제품의 지배적인 숫자는 불평등을 만족시킨다고 한다.

γ(G□H)≥(G)γ(H)γ.

단위 거리 그래프의 데카르트 산물은 또 다른 단위 거리 그래프다.^[5]

데카르트 제품 그래프는 선형으로 효율적으로 인식될 수 있다.^[6]

대수 그래프 이론

대수 그래프 이론은 데카르트 그래프 제품을 분석하는 데 사용될 수 있다. If the graph ${\displaystyle G_{1}}$ has ${\displaystyle n_{1}}$ vertices and the ${\displaystyle n_{1}\times n_{1}}$ adjacency matrix ${\displaystyle \mathbf {A} _{1}}$, and the graph ${\displaystyle G_{2}}$ has ${\displaystyle n_{2}}$ vertices and the ${\displaystyle n_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$}}: 인접$$ 행렬 $A{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$}},$$두 그래프의 데카르트 곱의 인접 행렬은 다음과 같다.

${\displaystyle \mathbf {A} _{1\square 2}=\mathbf {A} _{1}\otimes \mathbf {I} _{n_{2}}+\mathbf {I} _{n_{1}}\otimes \mathbf {A} _{2}}$,

여기서 $⊗{\displaystyle \otimes }$는 행렬의 Kronecker 제품을 나타내며$$ ${\displaystyle {}_{}}$ ${\$은 n${\displaystyle }$× n$${\$displaystystyle$ n$\times n}$ ID$$ 행렬을 나타낸다.^[7] 따라서 데카르트 그래프 제품의 인접 행렬은 인자의 인접 행렬의 Kronecker 합이다.

범주론

그래프를 객체가 정점이고 형태변수가 그래프에 있는 경로인 범주로 보는 것은 범주의 재미난 텐서 곱에 해당한다. 재미있는 텐서 산물에 해당한다. 그래프의 데카르트 산물은 그래프와 그래프 동형성의 범주를 대칭 폐쇄 단원형 범주로 바꾸는 두 개의 그래프 제품 중 하나이며, 다른 하나는 그래프의 텐서형 제품이다.^[8] 그래프의 데카르트 산물에 대한$$ 내부 홈${\displaystyle }$[${\displaystyle G}$, H ${\displaystyle ]}$ ${\displaystyle [G,H]}$은(는) $G{\displaystyle }$ {\$displaystyle G}$에서 H {\$displaystyle H}$까지의 동형성을 정점으로, 그들$$ 사이의 "비자연적 변환"을 에지로 한다.^[8]

역사

임리히&클라바샤르(2000년)에 따르면 1912년 화이트헤드와 러셀에 의해 카트리지어 그래프 생산물이 정의됐다. 그들은 나중에 특히 게르트 사비두시(1960년)에 의해 반복적으로 재발견되었다.

메모들

참조

• Aurenhammer, F.; Hagauer, J.; Imrich, W. (1992), "Cartesian graph factorization at logarithmic cost per edge", Computational Complexity, 2 (4): 331–349, doi:10.1007/BF01200428, MR 1215316.
• Feigenbaum, Joan; Hershberger, John; Schäffer, Alejandro A. (1985), "A polynomial time algorithm for finding the prime factors of Cartesian-product graphs", Discrete Applied Mathematics, 12 (2): 123–138, doi:10.1016/0166-218X(85)90066-6, MR 0808453.
• 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.
• Horvat, Boris; Pisanski, Tomaž (2010), "Products of unit distance graphs", Discrete Mathematics, 310 (12): 1783–1792, doi:10.1016/j.disc.2009.11.035, MR 2610282.
• Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8.
• Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Graphs and their Cartesian Products, A. K. Peters, ISBN 1-56881-429-1.
• Imrich, Wilfried; Peterin, Iztok (2007), "Recognizing Cartesian products in linear time", Discrete Mathematics, 307 (3–5): 472–483, doi:10.1016/j.disc.2005.09.038, MR 2287488.
• Kaveh, A.; Rahami, H. (2005), "A unified method for eigendecomposition of graph products", Communications in Numerical Methods in Engineering with Biomedical Applications, 21 (7): 377–388, doi:10.1002/cnm.753, MR 2151527.
• Sabidussi, G. (1957), "Graphs with given group and given graph-theoretical properties", Canadian Journal of Mathematics, 9: 515–525, doi:10.4153/CJM-1957-060-7, MR 0094810.
• Sabidussi, G. (1960), "Graph multiplication", Mathematische Zeitschrift, 72: 446–457, doi:10.1007/BF01162967, hdl:10338.dmlcz/102459, MR 0209177.
• Vizing, V. G. (1963), "The Cartesian product of graphs", Vycisl. Sistemy, 9: 30–43, MR 0209178.
• Weber, Mark (2013), "Free products of higher operad algebras", TAC, 28 (2): 24–65.

외부 링크

• Weisstein, Eric W. "Graph Cartesian Product". MathWorld.