आंशिक घन

Not to be confused with cubic graph.

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

इतिहास

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

उदाहरण

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

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