आंशिक घन

Not to be confused with त्रिविमीय आरेख.

आरेख सिद्धांत में आंशिक घन एक आरेख है जो आशिक घन के उप आरेख के लिए सममितीय है। दूसरे शब्दों में, आंशिक घन को एक आशिक घन के उप आरेख के साथ इस प्रकार से पहचाना जा सकता है कि आंशिक घन में किन्हीं दो शीर्षों के बीच की दूरी आशिक घन में उन शीर्षों के बीच की दूरी के समान है। समतुल्य रूप से आंशिक घन एक आरेख है जिसके शीर्षों को समान लंबाई के बिट श्रृंखला के साथ इस प्रकार से वर्गीकरण किया जा सकता है कि आरेख में दो शीर्षों के बीच की दूरी उनके वर्गीकरण के बीच हैमिंग दूरी के बराबर होती है। ऐसे वर्गीकरण को हैमिंग दूरी वर्गीकरण कहा जाता है यह आशिक घन में आंशिक घन के एक सममितीय अंत: स्थापन का प्रतिनिधित्व करता है।

इतिहास

फ़िरसोव (1965) आशिक घन में आरेख़ के सममितीय अंत: स्थापन का अध्ययन करने वाले पहले व्यक्ति थे। इस प्रकार के अंत: स्थापन को स्वीकार करने वाले आरेख़ को जोकोविच (1973) और विंकलर (1984) द्वारा चित्रित किया गया था और बाद में आंशिक घन नाम दिया गया था। आरेख़ के आशिक घन वर्गीकरण के अतिरिक्त समुच्चय के समूह की शब्दावली में एक ही संरचना पर शोध की एक अलग पंक्ति को कुज़्मिन & ओविचिनिकोव (1975) और फालमैग्ने & डीऑग्नन (1997) द्वारा प्रस्तुत किया गया था।

उदाहरण

एक आंशिक घन का एक उदाहरण जिसके शीर्ष पर हैमिंग वर्गीकरण है। यह आरेख भी एक माध्यिका आरेख है।

प्रत्येक पेड़ एक आंशिक घन है। मान लीजिए कि एक पेड़ T के किनारे m हैं और इन किनारों को (अपेक्षाकृत रूप से) 0 से m – 1 तक संख्याबद्ध करते हैं। अपेक्षाकृत रूप से पेड़ के लिए मूल शीर्ष r चुनें और प्रत्येक शीर्ष v को m बिट्स की एक स्ट्रिंग के साथ वर्गिकरण करें, जिसकी स्थिति में 1 है जब भी शीर्ष i, T में r से v के पथ पर स्थित होता है। उदाहरण के लिए, r के पास स्वयं एक सूचक होगा जो सभी शून्य बिट्स का होगा, उसके निकट एक 1-बिट के साथ सूचक होंगे जो किन्हीं दो वर्गिकरण के बीच हैमिंग की दूरी पेड़ में दो शीर्षों के बीच की दूरी है इसलिए इस वर्गिकरण से यह पता चलता है कि T एक आंशिक घन है।

प्रत्येक आशिक घन आरेख अपने आप में एक आंशिक घन है जिसे आशिक घन के आयाम के बराबर लंबाई के सभी अलग-अलग बिट श्रृंखला के साथ वर्गीकरण किया जा सकता है।

अधिक आंशिक उदाहरणों में निम्नलिखित सम्मिलित हैं:

• उस आरेख़ पर विचार करें जिसके शीर्ष लेबल में सभी संभव (2n + 1) -डिजिट बिटस्ट्रिंग होते हैं जिनमें या तो n या n + 1 नॉनज़रो बिट्स होते हैं, जहाँ दो कोने आसन्न होते हैं जब भी उनके लेबल एक बिट से भिन्न होते हैं। यह वर्गीकरण इन आरेख़ के एक आशिक घन (समान आसन्न स्थिति के साथ दी गई लंबाई के सभी बिटस्ट्रिंग्स का आरेख़) में एक अंत: स्थापन को परिभाषित करता है जो दूरी-संरक्षण के रूप में सामने आता है। परिणामी आरेख एक द्विदलीय केसर आरेख है n = 2 के साथ इस प्रकार से बने आरेख में 20 कोने और 30 किनारे होते हैं, और इसे Desargues आरेख कहा जाता है।
• सभी मध्य रेखांकन आंशिक घन हैं। ट्री और आशिक घन आरेख माध्यिका आरेख के उदाहरण हैं। चूंकि मध्य रेखांकन में वर्गआरेख, सिंप्लेक्स आरेख, और फाइबोनैचि घन के साथ-साथ परिमित वितरण श्रंखला के कवरिंग आरेख सम्मिलित हैं, ये सभी आंशिक घन हैं।
• यूक्लिडियन विमान में रेखाओं की व्यवस्था का समतलीय दोहरा आरेख एक आंशिक घन है। अधिक आम तौर पर, किसी भी संख्या के आयामों के यूक्लिडियन अंतरिक्ष में किसी भी हाइपरप्लेन व्यवस्था के लिए, व्यवस्था के प्रत्येक सेल के लिए एक शीर्ष और प्रत्येक दो आसन्न कोशिकाओं के लिए किनारे वाला आरेख एक आंशिक घन है।
• एक आंशिक घन जिसमें प्रत्येक शीर्ष के ठीक तीन पड़ोसी होते हैं, एक घन आरेख आंशिक घन के रूप में जाना जाता है। यद्यपि घन आंशिक घन के कई अनंत परिवार ज्ञात हैं, एक साथ कई अन्य छिटपुट उदाहरणों के साथ, एकमात्र ज्ञात घन आंशिक घन जो कि प्लेनर आरेख नहीं है, डेसार्गेस आरेख है।
• किसी भी antimatroid का अंतर्निहित आरेख, एंटीमैट्रोइड में प्रत्येक सेट के लिए एक शीर्ष और प्रत्येक दो सेट के लिए एक किनारा जो एक तत्व से भिन्न होता है, हमेशा एक आंशिक घन होता है।
• आंशिक घनों के किसी परिमित समुच्चय के रेखांकन का कार्तीय गुणनफल एक अन्य आंशिक घन होता है।
• एक पूर्ण आरेख का होमियोमोर्फिज्म (आरेख सिद्धांत) एक आंशिक घन है यदि और केवल अगर या तो प्रत्येक पूर्ण आरेख किनारे को दो-किनारे वाले पथ में उप-विभाजित किया गया है, या एक पूर्ण आरेख शीर्ष है जिसका घटना किनारों सभी अविभाजित हैं और सभी गैर- घटना किनारों को सम-लंबाई वाले पथों में उप-विभाजित किया गया है।

जोकोविच-विंकलर संबंध

आंशिक घनों के बारे में कई प्रमेय सीधे या परोक्ष रूप से ग्राफ के किनारों पर परिभाषित एक निश्चित द्विआधारी संबंध पर आधारित होते हैं। यह संबंध, जोकोविच (1973) द्वारा पहली बार वर्णित किया गया था और विंकलर (1984) द्वारा दूरी के संदर्भ में एक समान परिभाषा दी गई है, जिसे $\Theta$ द्वारा दर्शाया गया है। दो शीर्ष $e=\{x,y\}$ और $f=\{u,v\}$ को संबंध में परिभाषित किया गया है $\Theta$ लिखित $e\mathrel {\Theta } f$, यदि $d(x,u)+d(y,v)\not =d(x,v)+d(y,u)$ यह संबंध प्रतिवर्ती और सममित संबंध है, लेकिन सामान्य तौर पर यह सकर्मक संबंध नहीं है। $\Theta$ सकर्मक है। इस मामले में, यह एक तुल्यता संबंध बनाता है और प्रत्येक तुल्यता वर्ग आरेख के दो जुड़े हुए उप आरेख को एक दूसरे से अलग करता है। जोकोविच-विंकलर संबंध के प्रत्येक तुल्यता वर्ग को प्रत्येक लेबल का एक बिट निर्दिष्ट करके एक हैमिंग वर्गीकरण प्राप्त की जा सकती है; किनारों के एक समतुल्य वर्ग द्वारा अलग किए गए दो जुड़े उप आरेख में से एक में, सभी शीर्षों में उनके लेबल की स्थिति में 0 होता है, और दूसरे जुड़े उप आरेख में सभी शीर्षों में एक ही स्थिति में 1 होता है।

मान्यता

आंशिक घनों को पहचाना जा सकता है और $O(n^{2})$ समय में एक हैमिंग वर्गीकरण का निर्माण किया जा सकता है, जहाँ $n$ आरेख में शीर्षों की संख्या है। आंशिक घन को देखते हुए जोकोविच-विंकलर संबंध के समतुल्य वर्गों का निर्माण करना प्रत्यक्ष है कुल समय में प्रत्येक शीर्ष से एक चौड़ाई पहली खोज करके $O(nm)$ $O(n^{2})$ समय पहचान कलनविधि आरेख़ के माध्यम से एक ही पास में कई चौड़ाई वाली पहली खोज करने के लिए बिट-वर्गीकरण समानांतरवाद का उपयोग करके इसे गति देता है और फिर यह सत्यापित करने के लिए एक अलग कलनविधि प्रयुक्त करता है कि इस गणना का परिणाम एक वैध आंशिक घन वर्गीकरण है।

आयाम

एक आंशिक घन का सममितीय आयाम आशिक घन का न्यूनतम आयाम है जिस पर यह सममितीय रूप से अंतः स्थापित हो सकता है और जोकोविच-विंकलर संबंध के समतुल्य वर्गों की संख्या के बराबर है। उदाहरण के लिए एक का सममितीय आयाम $n$-शीर्ष इसके किनारों की संख्या $n-1$ है आशिक घन की समरूपता तक, इस आयाम के आशिक घन पर एक आंशिक घन का अंत: स्थापन अद्वितीय है।

प्रत्येक आशिक घन और इसलिए प्रत्येक आंशिक घन को एक पूर्णांक श्रंखला में समरूप रूप से स्थापित किया जा सकता है। आरेख़ का आयाम एक पूर्णांक श्रंखला का न्यूनतम आयाम है जिसमें आरेख़ को सममितीय रूप से अंतः स्थापित किया जा सकता है। श्रंखला आयाम सममितीय आयाम से अपेक्षाकृत रूप से छोटा हो सकता है उदाहरण के लिए, एक पेड़ के लिए यह पेड़ में पत्तियों की संख्या का आधा है और निकटतम पूर्णांक तक किसी भी आरेख़ का श्रंखला आयाम और न्यूनतम आयाम की श्रंखला अंत: स्थापन, सहायक आरेख़ में अधिकतम सममितीय आयाम के आधार पर एल्गोरिदम द्वारा बहुपद समय में पाया जा सकता है।

अधिक विशिष्ट संरचनाओं में अंत: स्थापन के आधार पर आंशिक घन के अन्य प्रकार के आयाम भी परिभाषित किए गए हैं।

रासायनिक आरेख सिद्धांत के लिए अनुप्रयोग

आशिक घन में आरेख़ के सममितीय अंत: स्थापन का रासायनिक आरेख़ सिद्धांत में एक महत्वपूर्ण अनुप्रयोग है। एक बेंजीनॉइड आरेख एक आरेख है जिसमें हेक्सागोनल श्रंखला में एक चक्र के अंदर और अंदर स्थित सभी कोने और किनारे होते हैं। इस प्रकार के आरेख बेंजीनॉइड हाइड्रोकार्बन के आणविक आरेख हैं, जो कार्बनिक अणुओं का एक बड़ा वर्ग है। ऐसा प्रत्येक आरेख एक आंशिक घन है। इस प्रकार के आरेख की एक हैमिंग वर्गीकरण का उपयोग संबंधित अणु के वियना सूचकांक की गणना करने के लिए किया जा सकता है, जिसका उपयोग उसके कुछ रासायनिक गुणों की भविष्यवाणी करने के लिए किया जा सकता है।

कार्बन, हीरा घन से बनी एक अलग आणविक संरचना भी आंशिक घन आरेख बनाती है।

संदर्भ

• Beaudou, Laurent; Gravier, Sylvain; Meslem, Kahina (2008), "Isometric embeddings of subdivided complete graphs in the hypercube" (PDF), SIAM Journal on Discrete Mathematics, 22 (3): 1226–1238, doi:10.1137/070681909, MR 2424849, S2CID 6332951
• Cabello, S.; Eppstein, D.; Klavžar, S. (2011), "The Fibonacci dimension of a graph", Electronic Journal of Combinatorics, 18 (1), P55, arXiv:0903.2507, Bibcode:2009arXiv0903.2507C, doi:10.37236/542, S2CID 9363180.
• Djoković, Dragomir Ž. (1973), "Distance-preserving subgraphs of hypercubes", Journal of Combinatorial Theory, Series B, 14 (3): 263–267, doi:10.1016/0095-8956(73)90010-5, MR 0314669.
• Eppstein, David (2005), "The lattice dimension of a graph", European Journal of Combinatorics, 26 (6): 585–592, arXiv:cs.DS/0402028, doi:10.1016/j.ejc.2004.05.001, S2CID 7482443.
• Eppstein, David (2006), "Cubic partial cubes from simplicial arrangements", Electronic Journal of Combinatorics, 13 (1), R79, arXiv:math.CO/0510263, doi:10.37236/1105, S2CID 8608953.
• Eppstein, David (2008), "Recognizing partial cubes in quadratic time", Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, pp. 1258–1266, arXiv:0705.1025, Bibcode:2007arXiv0705.1025E.
• Eppstein, David (2009), "Isometric diamond subgraphs", Proc. 16th International Symposium on Graph Drawing, Heraklion, Crete, 2008, Lecture Notes in Computer Science, vol. 5417, Springer-Verlag, pp. 384–389, arXiv:0807.2218, doi:10.1007/978-3-642-00219-9_37, S2CID 14066610.
• Falmagne, J.-C.; Doignon, J.-P. (1997), "Stochastic evolution of rationality" (PDF), Theory and Decision, 43 (2): 107–138, doi:10.1023/A:1004981430688, S2CID 117983644.
• Firsov, V.V. (1965), "On isometric embedding of a graph into a Boolean cube", Cybernetics, 1: 112–113, doi:10.1007/bf01074705, S2CID 121572742. As cited by Ovchinnikov (2011).
• Hadlock, F.; Hoffman, F. (1978), "Manhattan trees", Utilitas Mathematica, 13: 55–67. As cited by Ovchinnikov (2011).
• Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons, ISBN 978-0-471-37039-0, MR 1788124.
• Klavžar, Sandi; Gutman, Ivan; Mohar, Bojan (1995), "Labeling of benzenoid systems which reflects the vertex-distance relations" (PDF), Journal of Chemical Information and Computer Sciences, 35 (3): 590–593, doi:10.1021/ci00025a030.
• Kuzmin, V.; Ovchinnikov, S. (1975), "Geometry of preferences spaces I", Automation and Remote Control, 36: 2059–2063. As cited by Ovchinnikov (2011).
• Ovchinnikov, Sergei (2011), Graphs and Cubes, Universitext, Springer. See especially Chapter 5, "Partial Cubes", pp. 127–181.
• Winkler, Peter M. (1984), "Isometric embedding in products of complete graphs", Discrete Applied Mathematics, 7 (2): 221–225, doi:10.1016/0166-218X(84)90069-6, MR 0727925.