आंशिक घन

Not to be confused with cubic graph.

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

इतिहास

Firsov (1965) हाइपरक्यूब्स में ग्राफ़ के आइसोमेट्रिक एम्बेडिंग का अध्ययन करने वाले पहले व्यक्ति थे। इस तरह के एम्बेडिंग को स्वीकार करने वाले ग्राफ़ की विशेषता थी Djoković (1973) और Winkler (1984), और बाद में इन्हें आंशिक घन नाम दिया गया। ग्राफ़ के हाइपरक्यूब लेबलिंग के बजाय सेट के परिवार की शब्दावली में समान संरचनाओं पर शोध की एक अलग पंक्ति का अनुसरण किया गया Kuzmin & Ovchinnikov (1975) और Falmagne & Doignon (1997), दूसरों के बीच में।

उदाहरण

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

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

हर हाइपरक्यूब ग्राफ अपने आप में एक आंशिक क्यूब है, जिसे हाइपरक्यूब के आयाम के बराबर लंबाई के सभी अलग-अलग बिटस्ट्रिंग्स के साथ लेबल किया जा सकता है।

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

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

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

आंशिक घनों के बारे में कई प्रमेय सीधे या परोक्ष रूप से ग्राफ के किनारों पर परिभाषित एक निश्चित द्विआधारी संबंध पर आधारित होते हैं। यह संबंध, सबसे पहले द्वारा वर्णित है Djoković (1973) और द्वारा दूरी के संदर्भ में एक समान परिभाषा दी गई है Winkler (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.