ग्राफ़ के कार्तीय उत्पाद

रेखांकन का कार्तीय उत्पाद।

ग्राफ़ सिद्धांत में, कार्तीय गुणन G □ H ग्राफ़ G और H एक ऐसा ग्राफ़ है जो::

• G □ H का शीर्ष समुच्चय कार्तीय गुणनफल V(G) × V(H) है; और
• G □ H में दो शीर्ष (u,u' ) और (v,v' ) आसन्न हैं यदि और केवल यदि या तो
  • u = v और u', H में v' के सन्निकट है, या
  • u' = v' और u, G में v के सन्निकट है।

ग्राफ़ के कार्तीय उत्पाद को कभी-कभी ग्राफ़ का बॉक्स उत्पाद कहा जाता है [हैरी 1969]।

संचालन साहचर्य है, रेखांकन के रूप में (F □ G) □ H और F □ (G □ H) स्वाभाविक रूप से ग्राफ समरूपता हैं। संक्रिया क्रमविनिमेय है, रेखांकन के समरूपता तुल्यता वर्ग पर एक संक्रिया के रूप में, और अधिक दृढ़ता से रेखांकन G □ H और H □ G प्राकृतिक समरूपतावाद हैं, लेकिन यह ग्राफ लेबलिंग पर एक संचालन के रूप में क्रमविनिमेय नहीं है।

अंकन G × H का उपयोग अधिकांशत: ग्राफ़ के कार्तीय उत्पादों के लिए किया जाता है, लेकिन अब इसे ग्राफ़ के प्रदिश उत्पाद के रूप में जाने वाले अन्य निर्माण के लिए अधिक सामान्यतः उपयोग किया जाता है। चौकोर प्रतीक कार्तीय उत्पाद के लिए एक सहज और स्पष्ट संकेतन के रूप में अभिप्रेत है, क्योंकि यह दो किनारों के कार्तीय उत्पाद से उत्पन्न चार किनारों को दृष्टिगत रूप से दिखाता है।

उदाहरण

• दो किनारों का कार्तीय उत्पाद चार शीर्षों पर एक चक्र ग्राफ है: K₂□K₂ = C₄.
• K₂ का कार्तीय उत्पाद और एक पथ ग्राफ एक सीढ़ी ग्राफ है।
• दो पथ ग्राफ़ का कार्तीय उत्पाद एक जालक(ग्रिड) ग्राफ है।
• n किनारों का कार्तीय उत्पाद एक अतिविम है:

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

इस प्रकार, दो अतिविम ग्राफ का कार्तीय उत्पाद एक और अतिविम है: Q_i□Q_j = Q_i+j.

• दो माध्यिका ग्राफ का कार्तीय गुणनफल एक अन्य माध्यिका ग्राफ है।
• एन-प्रिज्म (ज्यामिति) के कोने और किनारों का ग्राफ कार्तीय उत्पाद ग्राफK₂□C_n है।
• रूक का ग्राफ दो पूर्ण ग्राफों का कार्तीय उत्पाद है।

गुण

यदि जुड़ा हुआ ग्राफ एक कार्तीय उत्पाद है, तो इसे प्रमुख कारकों के उत्पाद के रूप में विशिष्ट रूप से गुणनखंडित किया जा सकता है, ऐसे ग्राफ़ जिन्हें ग्राफ़ के उत्पादों के रूप में स्वयं विघटित नहीं किया जा सकता है। हालाँकि, इमरिच & कलवज़ार (2000) एक असंगत किए गए ग्राफ़ का वर्णन करें जिसे प्रधान ग्राफ़ के कार्तीय उत्पाद के रूप में दो अलग-अलग तरीकों से व्यक्त किया जा सकता है:

$(K_{1}+K_{2}+K_{2}^{2})\mathbin {\square } (K_{1}+K_{2}^{3})=(K_{1}+K_{2}^{2}+K_{2}^{4})\mathbin {\square } (K_{1}+K_{2}),$

जहां धन चिह्न(प्लस साइन) असंयुक्त संघ को दर्शाता है और उपरिलेख कार्तीय उत्पादों पर घातांक को दर्शाता है।

एक कार्तीय उत्पाद शीर्ष-सकर्मक ग्राफ है यदि और केवल यदि इसके प्रत्येक कारक हैं। एक कार्तीय उत्पाद द्विदलीय ग्राफ है यदि और केवल यदि इसके प्रत्येक कारक हैं। अधिक सामान्यतः, कार्तीय उत्पाद की रंगीन संख्या समीकरण को संतुष्ट करती है:

$\chi (G\mathbin {\square } H)=\max\{\chi (G),\chi (H)\}.$

हेडेनीमी का अनुमान रेखांकन के प्रदिश उत्पाद के लिए संबंधित समानता बताता है। कार्तीय उत्पाद की स्वतंत्रता संख्या इतनी आसानी से गणना नहीं की जाती है, लेकिन के रूप में वाइजिंग (1963) ने दिखाया कि यह असमानताओं को संतुष्ट करता है:

$\alpha (G)\alpha (H)+\min\{|V(G)|-\alpha (G),|V(H)|-\alpha (H)\}\leq \alpha (G\mathbin {\square } H)\leq \min\{\alpha (G)|V(H)|,\alpha (H)|V(G)|\}.$

वाइजिंग अनुमान कहता है कि कार्तीय उत्पाद की प्रभुत्व संख्या असमानता को संतुष्ट करती है:

$\gamma (G\mathbin {\square } H)\geq \gamma (G)\gamma (H).$

यूनिट दूरी ग्राफ़ का कार्तीय उत्पाद एक और यूनिट दूरी ग्राफ़ है।

कार्तीय उत्पाद रेखांकन को रैखिक समय में कुशलता से पहचाना जा सकता है।

बीजगणितीय ग्राफ सिद्धांत

कार्तीय ग्राफ उत्पाद का विश्लेषण करने के लिए बीजगणितीय ग्राफ सिद्धांत का उपयोग किया जा सकता है। यदि ग्राफ $G_{1}$ है $n_{1}$ शिखर और $n_{1}\times n_{1}$ सहखंडज आव्यूह $\mathbf {A} _{1}$, और ग्राफ $G_{2}$ है $n_{2}$ शिखर और $n_{2}\times n_{2}$ सहखंडज आव्यूह $\mathbf {A} _{2}$, तो दोनों ग्राफों के कार्तीय उत्पाद के आसन्न आव्यूह द्वारा दिया गया है।

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

जहाँ $\otimes$ आव्यूह के क्रोनकर उत्पाद को दर्शाता है और $\mathbf {I} _{n}$ दर्शाता है $n\times n$ तत्समक आव्यूह है। कार्तीय ग्राफ उत्पाद का आसन्न आव्यूह इसलिए कारकों के आसन्न आव्यूह का क्रोनकर योग है।

श्रेणी सिद्धांत

एक ग्राफ़ को एक श्रेणी (गणित) के रूप में देखना, जिनके ऑब्जेक्ट्स वर्टिसेस हैं और जिनके पथ आकारिता ग्राफ़ में हैं, रेखांकन का कार्टेशियन उत्पाद श्रेणियों के प्रदिश उत्पाद से मेल खाता है। ग्राफ़ का कार्तीय उत्पाद दो ग्राफ़ उत्पादों में से एक है जो ग्राफ़ और ग्राफ़ समरूपता की श्रेणी को एक सममित बंद मोनोइडल श्रेणी में बदल देता है (केवल सममित मोनोइडल के विपरीत), दूसरा ग्राफ़ का प्रदिश उत्पाद है। आंतरिक होम $[G,H]$ ग्राफ़ के कार्तीय उत्पाद के लिए ग्राफ़ समरूपताएँ हैं $G$ को $H$ शीर्ष के रूप में और अप्राकृतिक परिवर्तन उनके बीच किनारों के रूप में है।

इतिहास

इमरिच & कलवज़ार (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.