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

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

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

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

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

V(G $\square$) = H V(G) × V(H);

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

அல்லது

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

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

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

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

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

(F $\square$ G) $\square$ H = F $\square$ (G $\square$ H)

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

வரலாறு

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

எடுத்துக்காட்டுகள்

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

K₂ $\square$ K₂ = C₄.

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

K₂ $\square$ P_n

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

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

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

Q_i $\square$ Q_j = Q_i+j.

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

பண்புகள்

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

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

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

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

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

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

இயற்கணித கோட்டுருவியல்

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

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

இதில் $\otimes$ - அணிகளின் கிரொனேகேர் பெருக்கத்தின் (Kronecker product) குறியீடு; $\mathbf {I} _{n}$ - முற்றொருமை அணி.

மேற்கோள்கள்

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