கார்ட்டீசியன் பெருக்கற்பலன் (கோட்டுருவியல்)

கோட்டுருவியலில் G மற்றும் H ஆகிய இரு கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கற்பலன் (Cartesian product) G ${\displaystyle \square }$ H^[1] என்பது பின்வருமாறு அமையும் கோட்டுருவாகும்

• G ${\displaystyle \square }$ H இன் முனைகளின் கணமானது G மற்றும் H கோட்டுருக்களின் முனை கணங்களின் கார்ட்டீசியன் பெருக்கற்பலன்.

V(G ${\displaystyle \square }$) = H V(G) × V(H);

• u = v மற்றும் u' , v' இரண்டும் H இல் அடுத்துள்ள முனைகளாக

அல்லது

u' = v' மற்றும் u , v இரண்டும் G இல் அடுத்துள்ள முனைகளாக

இருந்தால், இருந்தால் மட்டுமே

• (u,u' ) , (v,v' ) இரண்டும் G ${\displaystyle \square }$ H இல் அடுத்துள்ள முனைகளாக இருக்கும்.

சிலசமயங்களில் கோட்டுருக்களின் பெருக்கற்பலன் "பெட்டிப் பெருக்கம்" (box product) எனவும் அழைக்கப்படுகிறது [Harary 1969].

(F ${\displaystyle \square }$ G) ${\displaystyle \square }$ H மற்றும் F ${\displaystyle \square }$ (G ${\displaystyle \square }$ H) கோட்டுருக்கள் இரண்டும் இயல்பாகவே சம அமைவியமுடையது என்பதால் அவற்றின் கார்ட்டீசியன் பெருக்கல் சேர்ப்புப் பண்பு உடையது.

(F ${\displaystyle \square }$ G) ${\displaystyle \square }$ H = F ${\displaystyle \square }$ (G ${\displaystyle \square }$ H)

கோட்டுருக்களின் சம அமைவிய சமானப் பகுதிகளின் மீது வரையறுக்கப்படும்போது கார்ட்டீசியன் பெருக்கல் செயலி பரிமாற்றுத்தன்மை கொண்டது; G ${\displaystyle \square }$ H மற்றும் H ${\displaystyle \square }$ G இரண்டும் வலிமையாக சம அமைவியமுடையது. ஆனால் பெயரிடப்பட்ட கோட்டுருக்களின் மீது வரையறுக்கப்படும் செயலியாக இது பரிமாற்றுத்தன்மையற்றது.

(Imrich & Klavžar 2000) இன் கூற்றுப்படி கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கற்பலன் 1912 ஆம் ஆண்டில் ஆல்பிரட் நார்த் வொய்ட்ஹெட் மற்றும் ரசலால் வரையறுக்கப்பட்டது. பின்னர் ஆஸ்திரேலியக் கணிதவியலாளர் "ஜெர்த் சபிதுசு"வால் (Gert Sabidussi (1960)) மீண்டும் கண்டறியப்பட்டது.

• இரு விளிம்புகளின் கார்ட்டீசியன் பெருக்கல் நான்கு முனைகளுடைய சுழற்சி கோட்டுரு

K₂ ${\displaystyle \square }$ K₂ = C₄.

• K₂ மற்றும் பாதை கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கல் ஒரு ஏணி கோட்டுரு.

K₂ ${\displaystyle \square }$ P_n

• இரு பாதை கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கல் ஒரு கட்டக் கோட்டுரு
• n விளிம்புகளின் கார்ட்டீசியன் பெருக்கல் ஒரு மீகனசதுரம்

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

இரு மீகனசதுரக் கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கல் மற்றொரு மீகனசதுரக் கோட்டுரு.

Q_i ${\displaystyle \square }$ Q_j = Q_i+j.

• இரு இடைநிலைமுனை கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கல் மற்றொரு இடைநிலைமுனை கோட்டுரு.
• K₂ மற்றும் C_n இரண்டின் கார்ட்டீசியன் பெருக்கல் n-பட்டகத்தின் முனைகள் மற்றும் விளிம்புகளின் கோட்டுரு
• இரு முழுக்கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கல் ரூக்கின் கோட்டுரு.

• ஒரு இணைப்புள்ள கோட்டுருவானது கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கலாக இருந்தால் அதனை பகாக் கோட்டுருக்களின் (மேற்கொண்டு கோட்டுருக்களின் பெருக்கலாகப் பிரிக்க முடியாத கோட்டுருக்கள்) பெருக்கலாகத் தனித்த முறையில் காரணிப்படுத்த முடியும். ^[2] ஒரு இணைப்பில்லா கோட்டுருவையும் இரு வேறுபட்ட வழிகளில் பகாக் கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கலாக எழுத முடியும் என விளக்கப்பட்டது(Imrich & Klavžar 2000):

(K₁ + K₂ + K₂²) ${\displaystyle \square }$ (K₁ + K₂³) = (K₁ + K₂² + K₂⁴) ${\displaystyle \square }$ (K₁ + K₂),

இதிலுள்ள + குறியானது இணப்பில்லா ஒன்றிப்பையும் மேலொட்டுகள் கார்ட்டீசியன் பெருக்கலின் அடுக்கையும் குறிக்கின்றன.

• கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கலிலுள்ள ஒவ்வொரு கோட்டுருவும் முனை-கடப்புக் கோட்டுருவாக இருந்தால், இருந்தால் மட்டுமே, கார்ட்டீசியன் பெருக்கற்பலனாகக் கிடைக்கும் கோட்டுருவும் முனை-கடப்புடையதாக இருக்கும்.^[3]

• கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கலிலுள்ள ஒவ்வொரு கோட்டுருவும் இருகூறு கோட்டுருவாக இருந்தால், இருந்தால் மட்டுமே, கார்ட்டீசியன் பெருக்கற்பலனாகக் கிடைக்கும் கோட்டுருவும் இருகூறு கோட்டுருவாக இருக்கும்.

• அலகு தொலைவு கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கற்பலனும் மற்றொரு அலகு தொலைவு கோட்டுரு.^[4]

கோட்டுரு ${\displaystyle G_{1}}$ இன் முனைகளின் எண்ணிக்கை ${\displaystyle n_{1}}$; ${\displaystyle n_{1}\times n_{1}}$ அண்மை அணி ${\displaystyle \mathbf {A} _{1}}$. கோட்டுரு ${\displaystyle G_{2}}$ இன் முனைகளின் எண்ணிக்கை ${\displaystyle n_{2}}$; ${\displaystyle n_{2}\times n_{2}}$ அண்மை அணி ${\displaystyle \mathbf {A} _{2}}$ எனில்: ${\displaystyle G_{1}}$, ${\displaystyle G_{2}}$ கோட்டுருக்களின் கார்ட்டீசியன் பெருக்கற்பலன் கோட்டுருவின் அண்மை அணி:

${\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 product) குறியீடு; ${\displaystyle \mathbf {I} _{n}}$ - முற்றொருமை அணி.^[5]

• 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.

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