रेखांकन का टेन्सर उत्पाद

From Vigyanwiki
रेखांकन का टेंसर उत्पाद।

ग्राफ सिद्धांत में, टेंसर उत्पाद {G × H} ग्राफ का (असतत गणित) G और H ऐसा ग्राफ है।

टेंसर उत्पाद को प्रत्यक्ष उत्पाद, क्रोनकर उत्पाद, श्रेणीबद्ध उत्पाद, कार्डिनल उत्पाद, संबंधपरक उत्पाद, कमजोर प्रत्यक्ष उत्पाद या संयोजन भी कहा जाता है। द्विआधारी संबंधों पर एक ऑपरेशन के रूप में, टेन्सर उत्पाद को अल्फ्रेड नॉर्थ व्हाइटहेड और बर्ट्रेंड रसेल द्वारा उनके प्रिंसिपिया मैथेमेटिका (1912) में प्रस्तुत किया गया था। यह ग्राफ़ के आसन्न मैट्रिक्स के क्रोनकर गुणनफल के बराबर भी है।[1]

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

उदाहरण

गुण

टेन्सर उत्पाद उत्पाद (श्रेणी सिद्धांत)| श्रेणी-सैद्धांतिक उत्पाद है जो रेखांकन और ग्राफ समरूपता की श्रेणी में है। यानी एक समरूपता G × H समरूपता की एक जोड़ी से मेल खाती है G और करने के लिए H विशेष रूप से, एक ग्राफ I एक समरूपता को स्वीकार करता है यदि और केवल अगर केवल यदि यह G और H में एक समाकारिता को स्वीकार करता है।

इसे देखने के लिए, एक दिशा में, समरूपता की एक जोड़ी का निरीक्षण करें fG : IG और fH : IH एक समरूपता उत्पन करता है।

दूसरी दिशा में, एक समरूपता f : IG × H को अनुमानों के समरूपता के साथ बनाया जा सकता है।

समरूपता प्राप्त करने के लिए G और करने के लिए H का आसन्न मैट्रिक्स G × H क्रोनकर उत्पाद है।

यदि एक ग्राफ को टेंसर उत्पाद के रूप में प्रदर्शित किया जा सकता है, तो कई अलग-अलग प्रतिनिधित्व हो सकते हैं (टेंसर उत्पाद अद्वितीय गुणनखंड को संतुष्ट नहीं करते हैं) लेकिन प्रत्येक प्रतिनिधित्व में इरेड्यूसिबल कारकों की समान संख्या होती है। इमरिच (1998) टेंसर उत्पाद ग्राफ़ को पहचानने और ऐसे किसी भी ग्राफ़ का गुणनखंड खोजने के लिए एक बहुपद समय एल्गोरिथ्म देता है।

या तो G या H द्विपक्षीय ग्राफ है, तो उनका टेंसर उत्पाद भी है। G × H जुड़ा हुआ है अगर और केवल अगर दोनों कारक जुड़े हुए हैं और कम से कम एक कारक द्विदलीय नहीं है।[3] विशेष रूप से द्विदलीय दोहरा आवरण G जुड़ा हुआ है अगर और केवल अगर G जुड़ा हुआ है और गैर-द्विपक्षीय है।

हेडेटनीमी अनुमान, जिसने एक टेन्सर उत्पाद की रंगीन संख्या के लिए एक सूत्र दिया था, यारोस्लाव शितोव (2019) द्वारा अप्रमाणित किया गया था।

ग्राफ़ का टेन्सर उत्पाद ग्राफ़ और ग्राफ़ समरूपता की श्रेणी को एक सममित मोनोइडल श्रेणी बंद मोनोइडल श्रेणी की संरचना से लैस करता है। माना G0 ग्राफ़ के शीर्षों के अंतर्निहित सेट को निरूपित करता है G. आंतरिक होम [G, H] के कार्य हैं f : G0H0 शीर्ष और किनारे के रूप में f : G0H0 को f' : G0H0 जब भी कोई किनारा {x, y} में H तात्पर्य {f (x), f ' (y)} से है।[4]

यह भी देखें

टिप्पणियाँ


संदर्भ

  • Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. (2008), "Graphs of Morphisms of Graphs", The Electronic Journal of Combinatorics, 15: A1.
  • 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.
  • Imrich, W. (1998), "Factoring cardinal product graphs in polynomial time", Discrete Mathematics, 192: 119–144, doi:10.1016/S0012-365X(98)00069-7, MR 1656730
  • Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8
  • Shitov, Yaroslav (May 2019), Counterexamples to Hedetniemi's conjecture, arXiv:1905.02167
  • Weichsel, Paul M. (1962), "The Kronecker product of graphs", Proceedings of the American Mathematical Society, 13 (1): 47–52, doi:10.2307/2033769, JSTOR 2033769, MR 0133816
  • Whitehead, A. N.; Russell, B. (1912), Principia Mathematica, Cambridge University Press, vol. 2, p. 384


बाहरी संबंध