Partial cube
ग्राफ सिद्धांत में, एक आंशिक घन एक ग्राफ है जो एक हाइपरक्यूब के उपग्राफ के लिए सममित है। दूसरे शब्दों में, एक आंशिक घन को एक अति घन के उपलेख से इस तरह से पहचाना जा सकता है कि आंशिक घन में किसी भी दो शीर्षों के बीच की दूरी अति घन में उन शीर्षों के बीच की दूरी के बराबर हो। समान रूप से, एक आंशिक घन एक ग्राफ है जिसके शीर्षों को समान लंबाई के बिट स्ट्रिंग्स के साथ इस तरह से लेबल किया जा सकता है कि ग्राफ में दो शीर्षों के बीच की दूरी उनके लेबल के बीच हैमिंग दूरी के बराबर हो। इस तरह के लेबलिंग को हैमिंग लेबलिंग कहा जाता है; यह एक हाइपरक्यूब में आंशिक घन के सममितीय एम्बेडिंग का प्रतिनिधित्व करता है। हाइपरक्यूब में ग्राफ के सममितीय एम्बेडिंग का अध्ययन करने वाला इतिहास पहला था। इस तरह के एम्बेडिंग को स्वीकार करने वाले ग्राफ की विशेषता और थी, और बाद में इन्हें आंशिक क्यूब्स नाम दिया गया। समान संरचनाओं पर अनुसंधान की एक अलग पंक्ति, ग्राफ के हाइपरक्यूब लेबलिंग के बजाय सेट के परिवारों की शब्दावली में, और, दूसरों के बीच। उदाहरण प्रत्येक वृक्ष एक आंशिक घन है। मान लीजिए कि एक पेड़ के किनारे हैं, और इन किनारों को (मनमाने ढंग से) एक से दूसरे तक गिनें। मनमाने ढंग से पेड़ के लिए एक जड़ शीर्ष चुनें, और प्रत्येक शीर्ष पर बिट्स की एक स्ट्रिंग के साथ लेबल करें जिसमें 1 की स्थिति हो जब भी किनारे से अंदर के रास्ते पर हो। उदाहरण के लिए, अपने आप में एक लेबल होगा जो सभी शून्य बिट्स होगा, इसके पड़ोसियों के पास एकल 1-बिट के साथ लेबल होंगे, आदि। फिर किसी भी दो लेबल के बीच हैमिंग दूरी पेड़ में दो शीर्षों के बीच की दूरी है, इसलिए यह लेबलिंग दिखाती है कि यह एक आंशिक घन है। प्रत्येक हाइपरक्यूब ग्राफ अपने आप में एक आंशिक घन है, जिसे हाइपरक्यूब के आयाम के बराबर लंबाई के सभी अलग-अलग बिटस्ट्रिंग के साथ लेबल किया जा सकता है। अधिक जटिल उदाहरणों में निम्नलिखित शामिल हैंः उस ग्राफ पर विचार करें जिसके शीर्ष लेबल में सभी संभावित-अंकीय बिटस्ट्रिंग होते हैं जिनमें या तो या गैर-शून्य बिट होते हैं, जहां दो शीर्ष बगल में होते हैं जब भी उनके लेबल एक बिट से भिन्न होते हैं। यह लेबलिंग इन ग्राफों को एक हाइपरक्यूब (एक दी गई लंबाई के सभी बिटस्ट्रिंग का ग्राफ, एक ही निकटता-स्थिति के साथ) में एम्बेड करने को परिभाषित करती है जो दूरी-संरक्षण साबित होती है। परिणामी ग्राफ एक द्विदलीय नेसर ग्राफ है; इस तरह से बने ग्राफ में 20 शीर्ष और 30 किनारे हैं, और इसे डेसारग्यूज ग्राफ कहा जाता है। सभी मध्य ग्राफ आंशिक घन हैं। पेड़ और हाइपरक्यूब ग्राफ मध्य ग्राफ के उदाहरण हैं। चूँकि मध्य ग्राफ में वर्ग ग्राफ, सिम्प्लेक्स ग्राफ और फिबोनाची क्यूब्स के साथ-साथ परिमित वितरण जाली के आवरण ग्राफ शामिल हैं, ये सभी आंशिक क्यूब्स हैं। यूक्लिडियन तल में रेखाओं की एक व्यवस्था का समतल दोहरा ग्राफ एक आंशिक घन है। अधिक आम तौर पर, यूक्लिडियन स्थान में किसी भी संख्या में आयामों की किसी भी हाइपरप्लेन व्यवस्था के लिए, वह ग्राफ जिसमें व्यवस्था की प्रत्येक कोशिका के लिए एक शीर्ष और प्रत्येक दो आसन्न कोशिकाओं के लिए एक किनारा होता है, एक आंशिक घन होता है। एक आंशिक घन जिसमें प्रत्येक शीर्ष के ठीक तीन पड़ोसी होते हैं, एक घन आंशिक घन के रूप में जाना जाता है। यद्यपि घन आंशिक घन के कई अनंत परिवार ज्ञात हैं, कई अन्य छिटपुट उदाहरणों के साथ, एकमात्र ज्ञात घन आंशिक घन जो एक समतलीय ग्राफ नहीं है, डेसारग्यूज ग्राफ है। किसी भी एंटीमैट्रॉइड का अंतर्निहित ग्राफ, जिसमें एंटीमैट्रॉइड में प्रत्येक सेट के लिए एक शीर्ष होता है और प्रत्येक दो सेट के लिए एक किनारा होता है जो एक तत्व से भिन्न होता है, हमेशा एक आंशिक घन होता है। आंशिक घन के किसी भी सीमित समूह का कार्टेशियन उत्पाद एक अन्य आंशिक घन है। एक पूर्ण ग्राफ का एक उपखंड एक आंशिक घन है यदि और केवल तभी जब प्रत्येक पूर्ण ग्राफ किनारे को दो-किनारे वाले पथ में विभाजित किया जाता है, या एक पूर्ण ग्राफ शीर्ष होता है जिसके सभी आपतित किनारे अविभाजित होते हैं और सभी गैर-घटना किनारों को सम-लंबाई वाले पथों में विभाजित किया गया है। जोकोविक-विंकलर संबंध आंशिक घन के बारे में कई प्रमेय प्रत्यक्ष या अप्रत्यक्ष रूप से ग्राफ के किनारों पर परिभाषित एक निश्चित द्विआधारी संबंध पर आधारित हैं। इस संबंध को, पहले द्वारा वर्णित किया गया है और द्वारा दूरी के संदर्भ में एक समतुल्य परिभाषा दी गई है, द्वारा दर्शाया गया है। दो किनारों को संबंध में परिभाषित किया गया है, लिखा गया है, यदि। यह संबंध प्रतिबिंबीत और सममित है, लेकिन सामान्य रूप से यह सकर्मक नहीं है। विंकलर ने दिखाया कि एक जुड़ा हुआ ग्राफ एक आंशिक घन है यदि और केवल तभी जब यह द्विदलीय हो और संबंध सकर्मक हो। इस मामले में, यह एक समतुल्यता संबंध बनाता है और प्रत्येक समतुल्यता वर्ग ग्राफ के दो जुड़े उपग्राफ को एक दूसरे से अलग करता है। जकोविक-विंकलर संबंध के समतुल्यता वर्गों में से प्रत्येक को प्रत्येक लेबल का एक बिट निर्दिष्ट करके हैमिंग लेबलिंग प्राप्त की जा सकती है; किनारों के समतुल्यता वर्ग द्वारा अलग किए गए दो जुड़े उपग्राफों में से एक में, सभी शीर्षों में उनके लेबल की उस स्थिति में 0 होता है, और दूसरे जुड़े उपग्राफ में सभी शीर्षों में एक ही स्थिति में 1 होता है। पहचान आंशिक क्यूब्स को पहचाना जा सकता है, और एक हैमिंग लेबलिंग का निर्माण किया जा सकता है, समय के साथ, ग्राफ में शीर्षों की संख्या कहाँ है। एक आंशिक घन को देखते हुए, कुल समय में प्रत्येक शीर्ष से एक चौड़ी पहली खोज करके जकोविक-विंकलर संबंध के समतुल्यता वर्गों का निर्माण करना सीधा है;-समय पहचान एल्गोरिथ्म बिट-स्तर समानांतरता का उपयोग करके इसे गति देता है ताकि ग्राफ के माध्यम से एक ही पास में कई चौड़ी पहली खोजों को किया जा सके, और फिर यह सत्यापित करने के लिए एक अलग एल्गोरिथ्म लागू किया जा सके कि इस गणना का परिणाम एक वैध आंशिक घन लेबलिंग है। एक आंशिक घन का सममितिक आयाम एक अति घन का न्यूनतम आयाम है जिस पर इसे सममितिक रूप से अंतर्निहित किया जा सकता है, और जोकोविक-विंकलर संबंध के समतुल्य वर्गों की संख्या के बराबर है। उदाहरण के लिए, एक-कशेरुकी वृक्ष का सममितीय आयाम उसके किनारों की संख्या है। इस आयाम के एक हाइपरक्यूब पर एक आंशिक घन का एम्बेडिंग अद्वितीय है, हाइपरक्यूब की समरूपता तक। प्रत्येक अति घन और इसलिए प्रत्येक आंशिक घन को एक पूर्णांक जाली में सममितीय रूप से एम्बेड किया जा सकता है। ग्राफ का जाली आयाम एक पूर्णांक जाली का न्यूनतम आयाम है जिसमें ग्राफ को सममितिक रूप से एम्बेड किया जा सकता है। जाली का आयाम सममितीय आयाम की तुलना में काफी छोटा हो सकता है; उदाहरण के लिए, एक पेड़ के लिए यह पेड़ में पत्तियों की संख्या का आधा है (निकटतम पूर्णांक तक गोल)। किसी भी ग्राफ का जाली आयाम, और न्यूनतम आयाम का जाली एम्बेडिंग, एक सहायक ग्राफ में अधिकतम मिलान के आधार पर एक एल्गोरिथ्म द्वारा बहुपद समय में पाया जा सकता है। अधिक विशिष्ट संरचनाओं में एम्बेडिंग के आधार पर आंशिक क्यूब्स के अन्य प्रकार के आयामों को भी परिभाषित किया गया है। रासायनिक ग्राफ सिद्धांत में अनुप्रयोग हाइपरक्यूब में ग्राफ के आइसोमेट्रिक एम्बेडिंग का रासायनिक ग्राफ सिद्धांत में एक महत्वपूर्ण अनुप्रयोग है। एक बेंजेनॉइड ग्राफ एक षट्कोणीय जाली में एक चक्र के अंदर और अंदर स्थित सभी शीर्षों और किनारों से युक्त एक ग्राफ है। इस तरह के ग्राफ बेंजेनॉइड हाइड्रोकार्बन के आणविक ग्राफ हैं, जो कार्बनिक अणुओं का एक बड़ा वर्ग है। इस तरह का प्रत्येक ग्राफ एक आंशिक घन है। इस तरह के ग्राफ की हैमिंग लेबलिंग का उपयोग संबंधित अणु के वीनर सूचकांक की गणना करने के लिए किया जा सकता है, जिसका उपयोग फिर इसके कुछ रासायनिक गुणों का अनुमान लगाने के लिए किया जा सकता है। कार्बन से बनी एक अलग आणविक संरचना, हीरा घन भी आंशिक घन ग्राफ बनाता है। टिप्पणियाँ संदर्भ। .. .. .. .. .. .. .. जैसा कि उद्धृत किया गया है। .. जैसा कि उद्धृत किया गया है। .. .. .. जैसा कि उद्धृत किया गया है। .. विशेष रूप से अध्याय 5, "आंशिक क्यूब्स", पृष्ठ देखें। 127-181। .. ग्राफ परिवार गणितीय रसायन विज्ञान द्विदलीय ग्राफ