View source for आंशिक घन

{{Short description|Graph isometric to a subgraph of a hypercube}}आरेख सिद्धांत में '''आंशिक घन''' एक आरेख है जो आशिक घन के उप आरेख के लिए [[आइसोमेट्री|सममितीय]] है।<ref>{{harvtxt|Ovchinnikov|2011}}, Definition 5.1, p. 127.</ref> दूसरे शब्दों में, आंशिक घन को एक आशिक घन के उप आरेख के साथ इस प्रकार से पहचाना जा सकता है कि आंशिक घन में किन्हीं दो शीर्षों के बीच की दूरी आशिक घन में उन शीर्षों के बीच की दूरी के समान है। जो समतुल्य रूप से आंशिक घन का एक आरेख है जिसके शीर्षों को समान लंबाई बिट श्रृंखला के साथ इस प्रकार से वर्गीकरण किया जा सकता है कि आरेख में दो शीर्षों के बीच की दूरी उनके वर्गीकरण के बीच हैमिंग दूरी के बराबर होती है। ऐसे वर्गीकरण को [[हैमिंग दूरी]] वर्गीकरण कहा जाता है यह आशिक घन में आंशिक घन के एक सममितीय [[एम्बेडिंग|अंत: स्थापन]] का प्रतिनिधित्व करता है।

== इतिहास ==
फ़िरसोव (1965) आशिक घन में आरेख़ के सममितीय अंत: स्थापन का अध्ययन करने वाले पहले व्यक्ति थे। इस प्रकार के अंत: स्थापन को स्वीकार करने वाले आरेख़ को {{harvtxt|जोकोविच|1973}} और {{harvtxt|विंकलर|1984}} द्वारा चित्रित किया गया था और बाद में आंशिक घन नाम दिया गया था। आरेख़ के आशिक घन वर्गीकरण के अतिरिक्त समुच्चय के समूह की शब्दावली में एक ही संरचना पर शोध की एक अलग पंक्ति को {{harvtxt|कुज़्मिन|ओविचिनिकोव|1975}} और {{harvtxt|फालमैग्ने|डीऑग्नन|1997}} द्वारा प्रस्तुत किया गया था।<ref>{{harvtxt|Ovchinnikov|2011}}, p. 174.</ref>
== उदाहरण ==
[[File:2SAT median graph.svg|thumb|upright=1.35|आंशिक घन का एक उदाहरण जिसके शीर्ष पर हैमिंग वर्गीकरण है। यह आरेख भी एक [[माध्यिका ग्राफ|माध्यिका आरेख]] है।]]प्रत्येक पेड़ एक आंशिक घन है। मान लीजिए कि एक पेड़ {{mvar|T}} का शीर्ष {{mvar|m}} हैं और इन शीर्षों को (अपेक्षाकृत रूप से) 0 से {{math|''m'' – 1}} तक संख्याबद्ध करते हैं। अपेक्षाकृत रूप से पेड़ के लिए मूल शीर्ष {{mvar|r}} चुनें और प्रत्येक शीर्ष v को m बिट्स की एक लंबाई के साथ वर्गिकरण करें, जिसकी स्थिति में 1 है जब भी शीर्ष {{mvar|i}}, {{mvar|T}} में {{mvar|r}} से {{mvar|v}} के पथ पर स्थित होता है। उदाहरण के लिए r के निकट स्वयं एक सूचक होता है जो सभी शून्य बिट्स का होता है उसके निकट एक 1-बिट के साथ सूचक होते है जो किन्हीं दो वर्गिकरण के बीच हैमिंग की दूरी पेड़ में दो शीर्षों के बीच की दूरी है इसलिए इस वर्गिकरण से यह पता चलता है कि T एक आंशिक घन है।

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

अधिक आंशिक उदाहरणों में निम्नलिखित सम्मिलित हैं:
* उस आरेख़ पर विचार करें जिसके शीर्ष वर्गीकरण में सभी संभव संख्याए {{math|(2''n'' + 1)}} बिट श्रृंखला हैं जिनमें {{mvar|n}} या {{math|''n'' + 1}} नॉनज़रो बिट्स होते हैं जहाँ दो शीर्ष आसन्न होते हैं जब भी उनके वर्गीकरण एक बिट से भिन्न होते हैं। तब यह वर्गीकरण इन आरेख़ के एक आशिक घन (समान आसन्न स्थिति के साथ दी गई लंबाई के सभी बिट श्रृंखला का आरेख़) में एक अंत: स्थापन को परिभाषित करता है जो दूरी-संरक्षण के रूप में सामने होता है। परिणामी आरेख एक द्विदलीय [[ केसर ग्राफ |केसर आरेख]] है जो {{math|1=''n'' = 2}} के साथ इस प्रकार से बने आरेख में 20 शीर्ष और 30 शीर्ष होते हैं और इसे [[Desargues ग्राफ|डीसार्गेस आरेख]] कहा जाता है।
*सभी मध्य रेखांकन आंशिक घन हैं।<ref>{{harvtxt|Ovchinnikov|2011}}, Section 5.11, "Median Graphs", pp. 163–165.</ref> पेंड और आशिक घन आरेख माध्यिका आरेख के उदाहरण हैं। चूंकि मध्य रेखांकन में [[वर्गग्राफ|वर्ग आरेख]], [[सिंप्लेक्स ग्राफ|संकेतन आरेख]] और फाइबोनैचि घन के साथ-साथ परिमित वितरण श्रंखला के आवरण आरेख सम्मिलित होते हैं ये सभी आंशिक घन हैं।
*[[यूक्लिडियन विमान|यूक्लिडियन समतल]] में [[रेखाओं की व्यवस्था|रेखाओं की स्थिति]] का समतलीय दोहरा आरेख एक आंशिक घन है। अधिक सामान्यतः किसी भी संख्या के आयामों के [[यूक्लिडियन अंतरिक्ष|यूक्लिडियन समष्टि]] में किसी भी [[हाइपरप्लेन व्यवस्था|अति समतल स्थिति]] के लिए, स्थिति के प्रत्येक कक्षा के लिए एक शीर्ष और प्रत्येक दो आसन्न कक्षों के लिए शीर्ष वाला आरेख एक आंशिक घन है।<ref>{{harvtxt|Ovchinnikov|2011}}, Chapter 7, "Hyperplane Arrangements", pp. 207–235.</ref>
*आंशिक घन जिसमें प्रत्येक शीर्ष के ठीक तीन घनिष्ठ होते हैं एक घन आरेख आंशिक घन के रूप में जाना जाता है। यद्यपि आंशिक घन के कई अनंत समुच्चय ज्ञात हैं और एक साथ कई अन्य उदाहरणों के साथ, एकमात्र ज्ञात घन आंशिक घन जो कि [[प्लेनर ग्राफ|तलीय आरेख]] नहीं है वह डेसार्गेस आरेख है।<ref>{{harvtxt|Eppstein|2006}}.</ref>
*किसी भी [[antimatroid|एंटीमैट्रोइड]] का अंतर्निहित आरेख, एंटीमैट्रोइड में प्रत्येक समुच्चय के लिए एक शीर्ष और प्रत्येक दो समुच्चय के लिए शीर्ष जो एक तत्व से भिन्न होता है सदैव एक आंशिक घन होता है।
*आंशिक घनों के किसी परिमित समुच्चय के रेखांकन का कार्तीय गुणनफल एक अन्य आंशिक घन होता है।<ref>{{harvtxt|Ovchinnikov|2011}}, Section 5.7, "Cartesian Products of Partial Cubes", pp. 144–145.</ref>
* एक पूर्ण आरेख का उपविभाजन आरेख सिद्धांत एक आंशिक घन है यदि और केवल यदि प्रत्येक पूर्ण आरेख शीर्ष को दो-शीर्ष वाले पथ में उप-विभाजित किया गया है या एक पूर्ण आरेख शीर्ष है जिसके घटना शीर्ष सभी अविभाजित हैं और सभी गैर- घटना शीर्षो को सम-लंबाई वाले पथों में उप-विभाजित किया गया है।{{sfnp|Beaudou|Gravier|Meslem|2008}}

== जोकोविच-विंकलर संबंध ==
आंशिक घनों के विषय में कई प्रमेय प्रत्यक्ष या परोक्ष रूप से आरेख के शीर्षों पर परिभाषित एक निश्चित [[द्विआधारी संबंध]] पर आधारित होते हैं। यह संबंध, {{harvtxt|जोकोविच|1973}} द्वारा पहली बार वर्णित किया गया था और {{harvtxt|विंकलर|1984}} द्वारा दूरी के संदर्भ में एक समान परिभाषा दी गई है, जिसे <math>\Theta</math> द्वारा दर्शाया गया है। दो शीर्ष <math>e=\{x,y\}</math> और <math>f=\{u,v\}</math> को संबंध में परिभाषित किया गया है <math>\Theta</math> लिखित <math>e\mathrel{\Theta}f</math>, यदि <math>d(x,u)+d(y,v)\not=d(x,v)+d(y,u)</math> यह संबंध प्रतिवर्ती और [[सममित संबंध]] है, लेकिन सामान्य रूप से यह [[सकर्मक संबंध]] नहीं है। <math>\Theta</math> सकर्मक है।<ref>{{harvtxt|Winkler|1984}}, Theorem&nbsp;4. See also {{harvtxt|Ovchinnikov|2011}}, Definition 2.13, p.29, and Theorem 5.19, p. 136.</ref> इस स्थिति में यह एक समतुल्य संबंध बनाता है और प्रत्येक समतुल्य वर्ग आरेख के दो सम्बद्ध उप आरेख को एक दूसरे से अलग करता है। जोकोविच-विंकलर संबंध के प्रत्येक [[तुल्यता संबंध|तुल्यता]] वर्ग को प्रत्येक वर्गीकारण का एक बिट निर्दिष्ट करके एक हैमिंग वर्गीकरण प्राप्त किया जा सकता है शीर्षों के एक समतुल्य वर्ग द्वारा अलग किए गए दो सम्बद्ध उप आरेख में से एक में सभी शीर्षों में उनके वर्गीकारण की स्थिति में 0 होता है और दूसरे सम्बद्ध उप आरेख में सभी शीर्षों में एक ही स्थिति में 1 होता है।

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

== आयाम ==
एक आंशिक घन का सममितीय आयाम आशिक घन का न्यूनतम आयाम है जिस पर यह सममितीय रूप से अंतः स्थापित हो सकता है और जोकोविच-विंकलर संबंध के समतुल्य वर्गों की संख्या के बराबर है। उदाहरण के लिए एक का सममितीय आयाम <math>n</math>-शीर्ष इसके शीर्षों की संख्या <math>n-1</math> है आशिक घन की समरूपता तक, इस आयाम के आशिक घन पर आंशिक घन का अंत: स्थापन अद्वितीय है।<ref>{{harvtxt|Ovchinnikov|2011}}, Section 5.6, "Isometric Dimension", pp. 142–144, and Section 5.10, "Uniqueness of Isometric Embeddings", pp. 157–162.</ref>

प्रत्येक आशिक घन और इसलिए प्रत्येक आंशिक घन को एक [[पूर्णांक जाली|पूर्णांक श्रंखला]] में समरूप रूप से स्थापित किया जा सकता है। आरेख़ का आयाम एक पूर्णांक श्रंखला का न्यूनतम आयाम है जिसमें आरेख़ को सममितीय रूप से अंतः स्थापित किया जा सकता है। श्रंखला आयाम सममितीय आयाम से अपेक्षाकृत रूप से छोटा हो सकता है उदाहरण के लिए, एक पेड़ के लिए यह पेड़ में पत्तियों की संख्या का आधा है और निकटतम पूर्णांक तक किसी भी आरेख़ का श्रंखला आयाम और न्यूनतम आयाम की श्रंखला अंत: स्थापन, सहायक आरेख़ में [[अधिकतम मिलान|अधिकतम सममितीय]] आयाम के आधार पर एल्गोरिदम द्वारा बहुपद समय में पाया जा सकता है।<ref>{{harvtxt|Hadlock|Hoffman|1978}}; {{harvtxt|Eppstein|2005}}; {{harvtxt|Ovchinnikov|2011}}, Chapter 6, "Lattice Embeddings", pp. 183–205.</ref>

अधिक विशिष्ट संरचनाओं में अंत: स्थापन के आधार पर आंशिक घन के अन्य प्रकार के आयाम भी परिभाषित किए गए हैं।<ref>{{harvtxt|Eppstein|2009}}; {{harvtxt|Cabello|Eppstein|Klavžar|2011}}.</ref>
== [[रासायनिक ग्राफ सिद्धांत|रासायनिक आरेख सिद्धांत]] के लिए अनुप्रयोग ==
आशिक घन में आरेख़ के सममितीय अंत: स्थापन का रासायनिक आरेख़ सिद्धांत में एक महत्वपूर्ण अनुप्रयोग है। बेंजीनॉइड आरेख एक आरेख है जिसमें [[हेक्सागोनल जाली|षट्कोणीय श्रंखला]] में एक चक्र के अंदर और अंदर स्थित सभी शीर्ष होते हैं। इस प्रकार के आरेख [[बेंजीनॉइड हाइड्रोकार्बन]] के [[आणविक ग्राफ|आणविक आरेख]] हैं जो कार्बनिक अणुओं का एक बड़ा वर्ग है। ऐसा प्रत्येक आरेख एक आंशिक घन है। इस प्रकार के आरेख की एक हैमिंग वर्गीकरण का उपयोग संबंधित अणु के [[वियना सूचकांक]] की गणना करने के लिए किया जा सकता है जिसका उपयोग उसके कुछ रासायनिक गुणों का पूर्वानुमान करने के लिए किया जा सकता है।<ref>{{harvtxt|Klavžar|Gutman|Mohar|1995}}, Propositions 2.1 and 3.1; {{harvtxt|Imrich|Klavžar|2000}}, p.&nbsp;60; {{harvtxt|Ovchinnikov|2011}}, Section 5.12, "Average Length and the Wiener Index", pp. 165–168.</ref> कार्बन, [[ हीरा घन |विषम कोणीय घन]] से बनी एक अलग आणविक संरचना भी आंशिक घन आरेख बनाती है।<ref>{{harvtxt|Eppstein|2009}}.</ref>
==टिप्पणियाँ==
{{reflist|colwidth=30em}}


==संदर्भ==
*{{citation
 | last1 = Beaudou | first1 = Laurent
 | last2 = Gravier | first2 = Sylvain
 | last3 = Meslem | first3 = Kahina
 | doi = 10.1137/070681909
 | issue = 3
 | journal = SIAM Journal on Discrete Mathematics
 | mr = 2424849
 | pages = 1226–1238
 | title = Isometric embeddings of subdivided complete graphs in the hypercube
 | volume = 22
 | year = 2008| s2cid = 6332951
 | url = https://hal.archives-ouvertes.fr/hal-00187039/file/clique_partial_cubes.pdf
 }}
*{{citation|title=The Fibonacci dimension of a graph|first1=S.|last1=Cabello|first2=D.|last2=Eppstein|author2-link=David Eppstein|first3=S.|last3=Klavžar|arxiv=0903.2507|journal=Electronic Journal of Combinatorics|volume=18|issue=1|at=P55|year=2011|doi=10.37236/542|bibcode=2009arXiv0903.2507C|s2cid=9363180 }}.
*{{citation
 | last1 = Djoković | first1 = Dragomir&nbsp;Ž.
 | title = Distance-preserving subgraphs of hypercubes
 | journal = [[Journal of Combinatorial Theory]] | series = Series&nbsp;B
 | volume = 14 | issue = 3 | year = 1973 | pages = 263–267
 | mr = 0314669 
 | doi = 10.1016/0095-8956(73)90010-5
 | doi-access = free}}.
*{{citation|first=David|last=Eppstein|authorlink=David Eppstein|arxiv=cs.DS/0402028|title=The lattice dimension of a graph|journal=European Journal of Combinatorics|volume=26|issue=6|pages=585–592|year=2005|doi=10.1016/j.ejc.2004.05.001|s2cid=7482443 }}.
*{{citation|title=Cubic partial cubes from simplicial arrangements|first=David|last=Eppstein|authorlink=David Eppstein|arxiv=math.CO/0510263 |journal=Electronic Journal of Combinatorics|volume=13|issue=1|at=R79|year=2006|doi=10.37236/1105|s2cid=8608953 |url=http://www.combinatorics.org/Volume_13/Abstracts/v13i1r79.html}}.
*{{citation|contribution=Recognizing partial cubes in quadratic time|first=David|last=Eppstein|authorlink=David Eppstein|arxiv=0705.1025 |title=Proc. 19th ACM-SIAM Symposium on Discrete Algorithms|year=2008|pages=1258–1266|bibcode=2007arXiv0705.1025E}}.
*{{citation|contribution=Isometric diamond subgraphs|first=David|last=Eppstein|authorlink=David Eppstein|arxiv=0807.2218 |title=[[International Symposium on Graph Drawing|Proc. 16th International Symposium on Graph Drawing, Heraklion, Crete, 2008]]|series=Lecture Notes in Computer Science|volume=5417|year=2009|pages=384–389|publisher=Springer-Verlag|doi=10.1007/978-3-642-00219-9_37|s2cid=14066610 }}.
*{{citation|last1=Falmagne|first1=J.-C.|author1-link=Jean-Claude Falmagne|last2=Doignon|first2=J.-P.|title=Stochastic evolution of rationality|journal=Theory and Decision|volume=43|pages=107–138|year=1997|issue=2|doi=10.1023/A:1004981430688|s2cid=117983644 |url=https://dipot.ulb.ac.be/dspace/bitstream/2013/303273/3/1997s_Falmagne_Doignon.pdf }}.
*{{citation|first=V.V.|last=Firsov|year=1965|title=On isometric embedding of a graph into a Boolean cube|journal=Cybernetics|volume=1|pages=112–113|doi=10.1007/bf01074705|s2cid=121572742 }}. As cited by {{harvtxt|Ovchinnikov|2011}}.
*{{citation|first1=F.|last1=Hadlock|first2=F.|last2=Hoffman|title=Manhattan trees|journal=Utilitas Mathematica|year=1978|volume=13|pages=55–67}}. As cited by {{harvtxt|Ovchinnikov|2011}}.
*{{citation
 | last1 = Imrich | first1 = Wilfried
 | last2 = Klavžar | first2 = Sandi
 | title = Product Graphs: Structure and Recognition
 | series = Wiley-Interscience Series in Discrete Mathematics and Optimization
 | publisher = John Wiley & Sons
 | year = 2000 | location = New York
 | isbn = 978-0-471-37039-0
 | mr = 1788124 
 }}.
*{{citation
 | last1 = Klavžar | first1 = Sandi
 | last2 = Gutman | first2 = Ivan
 | last3 = Mohar | first3 = Bojan | author3-link = Bojan Mohar
 | title = Labeling of benzenoid systems which reflects the vertex-distance relations
 | url = http://www.fmf.uni-lj.si/~klavzar/preprints/labeling-benzi.pdf
 | journal = Journal of Chemical Information and Computer Sciences
 | volume = 35 | issue = 3 | year = 1995 | pages = 590–593 | doi=10.1021/ci00025a030
 }}.
*{{citation|first1=V.|last1=Kuzmin|first2=S.|last2=Ovchinnikov|title=Geometry of preferences spaces I|journal=Automation and Remote Control|volume=36|year=1975|pages=2059–2063}}. As cited by {{harvtxt|Ovchinnikov|2011}}.
*{{citation|first=Sergei|last=Ovchinnikov|title=Graphs and Cubes|series=Universitext|publisher=Springer|year=2011}}. See especially Chapter 5, "Partial Cubes", pp. 127–181.
*{{citation
 | last1 = Winkler | first1 = Peter&nbsp;M. | authorlink = Peter Winkler
 | title = Isometric embedding in products of complete graphs
 | journal = Discrete Applied Mathematics
 | volume = 7 | issue = 2 | year = 1984 | pages = 221–225
 | mr = 0727925 
 | doi = 10.1016/0166-218X(84)90069-6
 | doi-access = free}}.

[[Category:Created On 20/03/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:गणितीय रसायन]]
[[Category:ग्राफ परिवार]]
[[Category:द्विदलीय रेखांकन]]