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

रेखांकन का कार्टेशियन उत्पाद।

ग्राफ सिद्धांत में, कार्टेशियन उत्पाद {{math|G □ H}ग्राफ का } (असतत गणित)। G और H ऐसा ग्राफ है कि:

• शीर्ष (ग्राफ सिद्धांत) का सेट G □ H कार्टेशियन उत्पाद है V(G) × V(H); और
• दो शिखर (u,u' ) और (v,v' ) में सटे हुए हैं G □ H अगर और केवल अगर या तो
  • u = v और u' लगी हुई है v' में H, या
  • u' = v' और u लगी हुई है v में G.

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

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

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

उदाहरण

• दो किनारों का कार्तीय उत्पाद चार शीर्षों पर एक चक्र ग्राफ है: K₂□क₂ = सी₄.
• K का कार्टेशियन उत्पाद₂ और एक पथ ग्राफ एक सीढ़ी ग्राफ है।
• दो पथ ग्राफ़ का कार्टेशियन उत्पाद एक ग्रिड ग्राफ़ है।
• एन किनारों का कार्टेशियन उत्पाद एक हाइपरक्यूब है:

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

इस प्रकार, दो हाइपरक्यूब ग्राफ का कार्टेशियन उत्पाद एक और हाइपरक्यूब है: क्यू_i□क्यू_j = क्यू_i+j.

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

गुण

यदि एक कनेक्टेड ग्राफ एक कार्टेशियन उत्पाद है, तो इसे प्रमुख कारकों के उत्पाद के रूप में विशिष्ट रूप से गुणनखंडित किया जा सकता है, ऐसे ग्राफ़ जिन्हें ग्राफ़ के उत्पादों के रूप में स्वयं विघटित नहीं किया जा सकता है। हालाँकि, Imrich & Klavžar (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)\}.$

Hedetniemi अनुमान रेखांकन के टेंसर उत्पाद के लिए संबंधित समानता बताता है। कार्तीय उत्पाद की स्वतंत्रता संख्या इतनी आसानी से गणना नहीं की जाती है, लेकिन के रूप में Vizing (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$ शीर्ष के रूप में और अप्राकृतिक परिवर्तन उनके बीच किनारों के रूप में।

इतिहास

के अनुसार Imrich & Klavžar (2000), ग्राफ़ के कार्तीय उत्पाद को 1912 में अल्फ्रेड नॉर्थ व्हाइटहेड और बर्ट्रेंड रसेल द्वारा परिभाषित किया गया था। उन्हें बार-बार बाद में फिर से खोजा गया, विशेष रूप से द्वारा Gert Sabidussi (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.