आंशिक घन

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

इतिहास

फ़िरसोव (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 शीर्ष होते हैं और इसे डीसार्गेस आरेख कहा जाता है।
• सभी मध्य रेखांकन आंशिक घन हैं। पेंड और आशिक घन आरेख माध्यिका आरेख के उदाहरण हैं। चूंकि मध्य रेखांकन में वर्ग आरेख, संकेतन आरेख और फाइबोनैचि घन के साथ-साथ परिमित वितरण श्रंखला के आवरण आरेख सम्मिलित होते हैं ये सभी आंशिक घन हैं।
• यूक्लिडियन समतल में रेखाओं की स्थिति का समतलीय दोहरा आरेख एक आंशिक घन है। अधिक सामान्यतः किसी भी संख्या के आयामों के यूक्लिडियन समष्टि में किसी भी अति समतल स्थिति के लिए, स्थिति के प्रत्येक कक्षा के लिए एक शीर्ष और प्रत्येक दो आसन्न कक्षों के लिए शीर्ष वाला आरेख एक आंशिक घन है।
• आंशिक घन जिसमें प्रत्येक शीर्ष के ठीक तीन घनिष्ठ होते हैं एक घन आरेख आंशिक घन के रूप में जाना जाता है। यद्यपि आंशिक घन के कई अनंत समुच्चय ज्ञात हैं और एक साथ कई अन्य उदाहरणों के साथ, एकमात्र ज्ञात घन आंशिक घन जो कि तलीय आरेख नहीं है वह डेसार्गेस आरेख है।
• किसी भी एंटीमैट्रोइड का अंतर्निहित आरेख, एंटीमैट्रोइड में प्रत्येक समुच्चय के लिए एक शीर्ष और प्रत्येक दो समुच्चय के लिए शीर्ष जो एक तत्व से भिन्न होता है सदैव एक आंशिक घन होता है।
• आंशिक घनों के किसी परिमित समुच्चय के रेखांकन का कार्तीय गुणनफल एक अन्य आंशिक घन होता है।
• एक पूर्ण आरेख का उपविभाजन आरेख सिद्धांत एक आंशिक घन है यदि और केवल यदि प्रत्येक पूर्ण आरेख शीर्ष को दो-शीर्ष वाले पथ में उप-विभाजित किया गया है या एक पूर्ण आरेख शीर्ष है जिसके घटना शीर्ष सभी अविभाजित हैं और सभी गैर- घटना शीर्षो को सम-लंबाई वाले पथों में उप-विभाजित किया गया है।

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

आंशिक घनों के विषय में कई प्रमेय प्रत्यक्ष या परोक्ष रूप से आरेख के शीर्षों पर परिभाषित एक निश्चित द्विआधारी संबंध पर आधारित होते हैं। यह संबंध, जोकोविच (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.