View source for हाइपरग्राफ में मिलान

{{short description|Set of hyperedges where every pair is disjoint}}

[[ग्राफ सिद्धांत]] में, [[ hypergraph |हाइपरग्राफ]] में '''सुमेलन''' [[हाइपरेज]] का एक समुच्चय है, जिसमें हर दो हाइपरेज [[अलग|असंयुक्त]] होते हैं। यह एक [[ग्राफ में मिलान|ग्राफ में सुमेलन]] की धारणा का विस्तार है।<ref name="lp">{{Cite Lovasz Plummer}}</ref>{{rp|466–470}} <ref>{{Cite book|last=Berge|first=Claude|title=रेखांकन और हाइपरग्राफ|publisher=North-Holland|year=1973|location=Amsterdam}}</ref>


== परिभाषा ==
याद रखें कि एक [[हाइपरग्राफ]] {{mvar|H}} युग्म {{math|(''V'', ''E'')}} है, जहां {{mvar|V}} शीर्षों का एक [[सेट (गणित)|समुच्चय]] है और {{mvar|E}} के [[उपसमुच्चय]] का एक समुच्चय है जिसे {{mvar|V}} ''हाइपरेज'' कहा जाता है। प्रत्येक हाइपरेज में एक या एक से अधिक शीर्ष हो सकते हैं।

''H'' में '''सुमेलन''' , ''E'' का एक उपसमुच्चय {{mvar|M}} है, जैसे कि ''M'' में प्रत्येक दो हाइपरेज e1 और e2 में एक रिक्त सर्वनिष्ठ है (कोई शीर्ष उभयनिष्ठ नहीं है)।

हाइपरग्राफ ''H'' की '''सुमेलन संख्या''' {{mvar|H}} में सुमेलन का सबसे बड़ा आकार है। इसे अक्सर {{math|ν(''H'')}} द्वारा दर्शाया जाता है।<ref name="lp" />{{rp|466}} <ref name=":1">{{Cite journal|last1=Aharoni|first1=Ron|last2=Kessler|first2=Ofra|date=1990-10-15|title=द्विदलीय हाइपरग्राफ के लिए हॉल के प्रमेय के संभावित विस्तार पर|journal=Discrete Mathematics|language=en|volume=84|issue=3|pages=309–313|doi=10.1016/0012-365X(90)90136-6|issn=0012-365X|doi-access=free}}</ref>

उदाहरण के लिए, {{mvar|V}} को समुच्चय {1,2,3,4,5,6,7} होने दें। ''V''  पर एक 3-एकसमान हाइपरग्राफ पर विचार करें (एक हाइपरग्राफ जिसमें प्रत्येक हाइपरेज में ठीक 3 शीर्ष होते हैं)। {{mvar|H}} को 4 हाइपरेज के साथ 3-एकसमान हाइपरग्राफ होने दें:

: {{math|{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} } }}

तब {{mvar|H}} आकार 2 के कई सुमेलनों को सम्मिलित करता है, उदाहरण के लिए:

: {{math|{ {1,2,3}, {4,5,6} } }}
: {{math|{ {1,4,5}, {2,3,6} } }}
हालाँकि, 3 हाइपरेज के किसी भी उपसमुच्चय में, उनमें से कम से कम दो प्रतिच्छेद करते हैं, इसलिए आकार 3 का कोई सुमेल नहीं है। इसलिए, H की सुमेलन संख्या 2 है।

== प्रतिच्छेदी हाइपरग्राफ{{Anchor|intersecting}} ==
एक हाइपरग्राफ {{math|1=''H'' = (''V'', ''E'')}} को प्रतिच्छेदी कहा जाता है यदि ''E'' में प्रत्येक दो हाइपरेज में एक शीर्ष उभयनिष्ठ है। एक हाइपरग्राफ {{mvar|H}} प्रतिच्छेद कर रहा है [[अगर और केवल अगर]] इसमें दो या दो से अधिक हाइपरेज के साथ कोई सुमेलित नहीं है, अगर और केवल अगर {{math|1=ν(''H'') = 1}}|<ref name=":2" />


== एक विशेष स्थिति के रूप में एक ग्राफ में सुमेलन ==
[[आत्म पाश|स्वपाश]] के बिना एक ग्राफ केवल 2-एकसमान हाइपरग्राफ है: प्रत्येक किनारे को दो शीर्षों के समुच्चय के रूप में माना जा सकता है जो इसे जोड़ता है। उदाहरण के लिए, यह 2-एकसमान हाइपरग्राफ 4 शीर्षों {1,2,3,4} और 3 किनारों के साथ एक ग्राफ को प्रस्तुत करता है:

: {{math|{ {1,3}, {1,4}, {2,4} } }}
उपरोक्त परिभाषा के अनुसार, ग्राफ़ में सुमेलन किनारों का एक समुच्चय {{mvar|M}}  है, जैसे कि ''M'' में प्रत्येक दो किनारों में एक रिक्त सर्वनिष्ठ है। यह कथन तुल्य है कि ''M'' में कोई भी दो किनारे समान शीर्ष से संलग्न नहीं हैं;  यह यथार्थत: एक [[ग्राफ़ में सुमेलन]] की परिभाषा है।

== [[आंशिक मिलान|भिन्नात्मक सुमेलन]] ==
हाइपरग्राफ में एक [[भिन्नात्मक सुमेलन|'''भिन्नात्मक सुमेलन''']] एक ऐसा फलन है जो प्रत्येक हाइपरेज को [0,1] में एक भिन्न प्रदान करता है, जैसे कि ''V'' में प्रत्येक शीर्ष {{mvar|v}} के लिए, ''v'' वाले हाइपरेज के भिन्नों का योग अधिकतम 1 है। एक सुमेलन भिन्नात्मक सुमेलन की एक विशेष स्थिति है जिसमें सभी भिन्न या तो 0 या 1 होते हैं। भिन्नात्मक सुमेलन का आकार सभी हाइपरेज के भिन्नों का योग होता है।

हाइपरग्राफ ''H'' की '''भिन्नात्मक सुमेलन संख्या''' {{mvar|H}} में भिन्नात्मक सुमेलन का सबसे बड़ा आकार है| इसे अक्सर ''ν*(H)'' द्वारा निरूपित किया जाता है।<ref name=":1" />

चूंकि सुमेलन प्रत्येक हाइपरग्राफ ''H'' के लिए भिन्नात्मक सुमेलन की एक विशेष स्थिति है: <blockquote>सुमेलन-संख्या({{mvar|H}}) ≤ भिन्नात्मक -सुमेलन-संख्या ({{mvar|H}})</blockquote>
प्रतीकात्मक रूप से, यह सिद्धांत लिखा गया है:
:<math>\nu(H) \leq \nu^*(H) </math>
सामान्य तौर पर, भिन्नात्मक सुमेलन संख्या सुमेलन संख्या से बड़ी हो सकती है। ज़ोल्टन फ़्यूरेडी द्वारा एक प्रमेय<ref name=":2">{{Cite journal|last=Füredi|first=Zoltán|date=1981-06-01|title=समान हाइपरग्राफ में अधिकतम डिग्री और आंशिक मिलान|journal=Combinatorica|language=en|volume=1|issue=2|pages=155–162|doi=10.1007/BF02579271|s2cid=10530732|issn=1439-6912}}</ref> भिन्नात्मक-सुमेलन-संख्या (''H'')/ सुमेलन-संख्या(''H'') अनुपात पर उच्च परिबद्ध प्रदान करती है: 

यदि ''H'' में प्रत्येक हाइपरेज में अधिकतर ''r'' शीर्ष होते हैं, तो

* <p><math>\frac{\nu^*(H)}{ \nu (H)} \leq r-1+ \frac{1}{r}.</math></p><p>विशेष रूप से, एक साधारण ग्राफ में:<ref>{{Cite journal|last=Lovász|first=L.|date=1974|editor-last=Berge|editor-first=Claude|editor2-last=Ray-Chaudhuri|editor2-first=Dijen|title=हाइपरग्राफ के लिए मिनिमैक्स प्रमेय|journal=Hypergraph Seminar|series=Lecture Notes in Mathematics|volume=411|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=111–126|doi=10.1007/BFb0066186|isbn=978-3-540-37803-7}}</ref></p><p><math>\frac{\nu^*(H)}{ \nu (H)} \leq \frac{3}{2}.</math></p>
** असमिका स्पष्ट (शार्प) है: Hr को r-एकसमान [[परिमित प्रक्षेपी तल]] होने दें। तब  {{math|1=''ν''(''H''{{sub|''r''}}) = 1}} चूंकि प्रत्येक दो हाइपरेज एक दूसरे को प्रतिच्छेद करते हैं, और {{math|1=''ν''*(''H''{{sub|''r''}}) = ''r'' – 1 + {{sfrac|1|''r''}}}} भिन्नात्मक सुमेलन द्वारा जो भार प्रदान करता है {{math|{{sfrac|1|''r''}}}} प्रत्येक हाइपरेज के लिए (यह एक सुमेलन है क्योंकि प्रत्येक शीर्ष ''r''  हाइपरेज में सम्मिलित है,और इसका आकार {{math|''r'' – 1 + {{sfrac|1|''r''}}}} है चूँकि वहाँ r2 - r + 1 हाइपरेज हैं)। इसलिए अनुपात यथार्थत: {{math|''r'' – 1 + {{sfrac|1|''r''}}}} है |
* यदि {{mvar|r}} ऐसा है कि {{mvar|r}}-एकसमान परिमित प्रक्षेपी तल उपस्थित नहीं है (उदाहरण के लिए, {{math|1=''r'' = 7}}), तो एक प्रबल असमता रखती है: <p><math>\frac{\nu^*(H)}{\nu (H)} \leq r-1.</math></p>
* यदि {{mvar|H}} {{mvar|r}}-विभक्त है (शीर्षों को ''r'' भागों में विभाजित किया गया है और प्रत्येक हाइपरेज में प्रत्येक भाग से एक शीर्ष सम्मिलित है), तो: <p><math>\frac{\nu^*(H)}{\nu (H)} \leq r-1.</math></p><p>विशेष रूप से, द्विभाजित ग्राफ में, {{math|1=''ν''*(''H'') = ''ν''(''H'')}} है | यह एंड्रस ग्यारफास द्वारा सिद्ध किया गया था।<ref name=":2" /></p>
** असमिका स्पष्ट है: {{mvar|H{{sub|r-}}}}क्रम r - 1 का [[छोटा प्रोजेक्टिव प्लेन|रुंडित प्रक्षेपी तल]] हो | फिर {{math|1=''ν''(''H''{{sub|''r''-}}) = 1}} चूंकि हर दो हाइपरेज एक दूसरे को प्रतिच्छेद करते हैं, और {{math|1=''ν''*(''H''{{sub|''r''-}}) = ''r'' – 1}} भिन्नात्मक सुमेलन द्वारा जो भार प्रदान करता है {{math|{{sfrac|1|''r''}}}} प्रत्येक हाइपरेज के लिए ( {{math|''r''{{sup|2}} – ''r''}} हाइपरेज हैं)।

== पूर्ण सुमेलन ==
एक सुमेलन {{mvar|M}} को '''पूर्ण''' कहा जाता है यदि ''V'' में हर शीर्ष ''v M'' के ठीक एक हाइपरेज में सम्मिलित है। यह एक ग्राफ में [[पूर्ण सुमेलन]] की धारणा का स्वाभाविक विस्तारण है।

एक भिन्नात्मक सुमेलन ''M'' को पूर्ण कहा जाता है यदि {{mvar|V}}  में प्रत्येक शीर्ष v के लिए, {{mvar|M}}  युक्त {{mvar|v}}  में हाइपरेज के भिन्नों का योग वास्तव में 1 है।

एक हाइपरग्राफ ''H'' पर विचार करें जिसमें प्रत्येक हाइपरेज में अधिकतम {{mvar|n}} शीर्ष होते हैं। यदि {{mvar|H}} पूर्ण भिन्नात्मक सुमेलन को प्रविष्ट करता है, तो उसकी भिन्नात्मक सुमेलन संख्या कम से कम  {{math|{{frac|{{abs|''V''}} |''n''}}}} होती है| यदि  {{mvar|H}} में प्रत्येक हाइपरेज में यथार्थत: {{mvar|n}} शीर्ष होते हैं, तो इसकी भिन्नात्मक सुमेलन संख्या ठीक {{math|{{frac|{{abs|''V''}} |''n''}}}} पर होती है| <ref name=":0">{{Cite journal|last1=Nyman|first1=Kathryn|last2=Su|first2=Francis Edward|last3=Zerbib|first3=Shira|date=2020-01-02|title=कई टुकड़ों के साथ उचित विभाजन|url=http://www.sciencedirect.com/science/article/pii/S0166218X1930561X|journal=Discrete Applied Mathematics|volume=283|pages=115–122|language=en|arxiv=1710.09477|doi=10.1016/j.dam.2019.12.018|s2cid=119602376|issn=0166-218X}}</ref> {{Rp|sec.2}} यह इस तथ्य का व्यापकीकरण है कि, किसी ग्राफ़ में, एक पूर्ण सुमेलन का आकार{{math|{{frac|{{abs|''V''}} |2}}}} है |

शीर्षों का एक समुच्चय {{mvar|V}}  दिया गया है, ''V'' के उपसमुच्चय का एक संग्रह {{mvar|E}} संतुलित कहा जाता है अगर हाइपरग्राफ {{math|(''V'',''E'')}} एक पूर्ण भिन्नात्मक सुमेलन स्वीकार करता है।

उदाहरण के लिए, अगर {{math|1=''V'' = {1,2,3,a,b,c} }} और {{math|1=''E'' = { {1,a}, {2,a}, {1,b}, {2,b}, {3,c} },}} तब {{mvar|E}} पूर्ण भिन्नात्मक सुमेलन के साथ संतुलित है {{math|{ 1/2, 1/2, 1/2, 1/2, 1 }.}}

हाइपरग्राफ में एक पूर्ण सुमेलन के अस्तित्व के लिए विभिन्न पर्याप्त शर्तें हैं:

* [[हाइपरग्राफ के लिए हॉल-टाइप प्रमेय]] - समीप (नैबर) के समुच्चय के आधार पर हॉल के विवाह (मेरिज) प्रमेय के अनुरूप पर्याप्त शर्तें प्रस्तुत करता है।
* [[हाई-डिग्री हाइपरग्राफ में सटीक मिलान|उच्च-घात हाइपरग्राफ में]] [[पूर्ण सुमेलन]] - शीर्षों की घात के आधार पर [[हैमिल्टोनियन चक्रों पर डिराक के प्रमेय]] के समान पर्याप्त शर्तें प्रस्तुत करता है।
* [[पीटर कीवाश|कीवाश]] और माइक्रॉफ्ट ने हाइपरग्राफ सुमेलन के लिए एक ज्यामितीय सिद्धांत विकसित किया।<ref>{{Cite book|last1=Keevash|first1=Peter|url=https://www.ams.org/memo/1098/|title=हाइपरग्राफ मिलान के लिए एक ज्यामितीय सिद्धांत|last2=Mycroft|first2=Richard|date=2015-01-01|publisher=American Mathematical Society|isbn=978-1-4704-0965-4|series=Memoirs of the American Mathematical Society|volume=233|language=en}}</ref>


== संतुलित समुच्चय-परिवार ==
ग्राउंड समुच्चय {{mvar|V}} पर एक [[समुच्चय-परिवार]] ''E'' को कहा जाता है ({{mvar|V}} के संबंध में ) अगर हाइपरग्राफ {{math|1=''H'' = (''V'', ''E'')}} पूर्ण भिन्नात्मक सुमेलन मान लेता है।<ref name=":0" /> {{Rp|sec.2}}

उदाहरण के लिए, शीर्ष समुच्चय {{math|1=''V'' = {1,2,3,a,b,c} }} और किनारा समुच्चय {{math|1=''E'' = {1-a, 2-a, 1-b, 2-b, 3-c<nowiki>}</nowiki>}} मानना है| {{mvar|E}} संतुलित है, क्योंकि भार {1/2, 1/2, 1/2, 1/2, 1} के साथ एक पूर्ण भिन्नात्मक सुमेलन है|

== अधिकतम सुमेलन की गणना ==
हाइपरग्राफ में अधिकतम-गणनांक सुमेलन जाँच परिणाम की समस्या, इस प्रकार गणना करना <math>\nu(H)</math>, 3-एकसमान हाइपरग्राफ के लिए भी एनपी-ठोस है ([[3-आयामी मिलान|3-विमीय]] सुमेलन देखें)। यह सरल (2-एकसमान) ग्राफ़ की स्थिति के विपरीत है जिसमें बहुपद समय में [[अधिकतम-गणनांक सुमेलन]] की गणना की जा सकती है।

== सुमेलन और आवरण ==
[[हाइपरग्राफ|''हाइपरग्राफ'']] {{math|1=''H'' = (''V'', ''E'')}} में एक [[शीर्ष-आवरण|''शीर्ष-आवरण'']] ''V'' का एक उपसमुच्चय ''T'' है, जैसे कि प्रत्येक हाइपरेज में ''T'' का कम से कम एक शीर्ष होता है {{mvar|T}} (इसे [[अनुप्रस्थ]] या [[हिटिंग सेट|आघाती]] [[समुच्चय]] भी कहा जाता है, और यह समुच्चय आवरण के तुल्य है)। यह एक ग्राफ में ''[[वर्टेक्स कवर|शीर्ष-आवरण]]''  की धारणा का व्यापकीकरण है।

हाइपरग्राफ {{mvar|H}} की '''शीर्ष-आवरण संख्या''' का सबसे छोटा आकार है। तिर्यक रेखा के लिए इसे अक्सर {{math|''τ''(''H'')}},<ref name="lp" />{{rp|466}}  से दर्शाया जाता है।

एक '''भिन्नात्मक''' <small>'''शीर्ष-आवरण'''</small> एक ऐसा फलन है जो ''V'' में प्रत्येक शीर्ष को भार नियत करता है, जैसे कि ''E'' में प्रत्येक  हाइपरेज {{mvar|e}} के लिए, ''e'' में शीर्षों के भिन्नों का योग कम से कम 1 है। शीर्ष-आवरण एक भिन्नात्मक शीर्ष-आवरण की एक विशेष स्थिति है जिसमें सभी भार या तो 0 या 1 हैं। भिन्नात्मक शीर्ष-आवरण का आकार सभी शीर्षों के भिन्नों का योग होता है।

हाइपरग्राफ {{mvar|H}} की '''शीर्ष-आवरण संख्या''' ''H'' में एक भिन्नात्मक शीर्ष-आवरण का सबसे छोटा आकार है। इसे अक्सर {{math|''τ''*(''H'')}} से दर्शाया जाता है।

चूँकि प्रत्येक हाइपरग्राफ ''H'' के लिए शीर्ष-आवरण एक भिन्नात्मक शीर्ष-आवरण की एक विशेष स्थिति है:

रैखिक प्रोग्रामन द्वैत का तात्पर्य है कि, प्रत्येक हाइपरग्राफ H के लिए:

भिन्नात्मक-सुमेलन-संख्या (''H'') = भिन्नात्मक-शीर्ष-आवरण- संख्या (''H'')।<ref name=":2" />

इसलिए, हर हाइपरग्राफ H के लिए::<math>\nu(H) \leq \nu^*(H) =  \tau^*(H)\leq  \tau(H) </math>

यदि {{mvar|H}} में हाइपरेज का आकार अधिकतम ''r'' है, तो अधिकतम सुमेलन में सभी हाइपरेज का सम्मिलन एक शीर्ष-आवरण है (यदि कोई विवृत हाइपरेज था, तो हम इसे सुमेलन में जोड़ सकते थे)। इसलिए:
:<math>\tau(H)\leq r\cdot \nu(H).</math>
यह असमता ठोस (टाइट) है: समता रखती है, उदाहरण के लिए, जब {{mvar|V}}  में {{math|''r''⋅''ν''(''H'') + ''r'' – 1}} शीर्ष होते हैं और {{mvar|E}} में {{mvar|r}} शीर्षों के सभी उपसमुच्चय होते हैं।

हालाँकि, सामान्य रूप से {{math|''τ''*(''H'') <  ''r''⋅''ν''(''H'')}}, चूँकि  {{math|''ν''*(''H'') < ''r''⋅''ν''(''H'')}}; ऊपर [[भिन्नात्मक सुमेलन]] देखें।

[[रायसर का अनुमान|रायसर का अनुमानित कथन]] कहता है कि, प्रत्येक {{mvar|r}}-विभक्त {{mvar|r}}-एकसमान में:
:<math>\tau (H)\leq (r-1) \nu(H).</math>
अनुमानित कथन की कुछ विशेष स्थिति सिद्ध हुई हैं; [[रायसर का अनुमानित कथन]] देखें।

== कोनिग के गुण ==
एक हाइपरग्राफ में '''कोनिग के गुण''' होते है यदि इसकी अधिकतम सुमेलन संख्या इसकी न्यूनतम शीर्ष-आवरण संख्या के तुल्य होती है, अर्थात् यदि {{math|1=''ν''(''H'') = ''τ''(''H'')}} |[[कोनिग-एगेर्वरी प्रमेय]] से पता चलता है कि प्रत्येक [[द्विभाज्य ग्राफ]] में कोनिग गुण होता है। इस प्रमेय को हाइपरग्राफ तक विस्तारित करने के लिए, हमें द्विभाज्यता की धारणा को हाइपरग्राफ तक विस्तारित करने की आवश्यकता होती है।<ref name="lp" />{{rp|468}}

एक साधारण व्यापकीकरण इस प्रकार है। एक हाइपरग्राफ को '''2-'''रंगीन कहा जाता है अगर इसके शीर्ष 2-रंगीन के हो सकते हैं ताकि प्रत्येक हाइपरेज (आकार कम से कम 2) में प्रत्येक रंग का कम से कम एक शीर्ष हो। एक वैकल्पिक पद का [[संपत्ति बी|गुण]] ''B'' है। एक साधारण ग्राफ द्विभाज्य है अगर यह 2-रंगीन है। हालांकि, कोनिग के गुण के बिना 2-रंगीन हाइपरग्राफ होते हैं। उदाहरण के लिए, {{math|1=''V'' = {1,2,3,4} }} के साथ हाइपरग्राफ पर मानना है जिसमें सभी त्रिक {{math|1=''E'' = { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} <nowiki>}</nowiki>}} | यह 2-रंगीन है, उदाहरण के लिए, हम {{math|{1,2} }}नीला और {3,4} सफेद रंग कर सकते हैं। हालाँकि, इसकी सुमेलन संख्या 1 और शीर्ष-आवरण संख्या 2 है।

एक प्रबल व्यापकीकरण इस प्रकार है। एक हाइपरग्राफ {{math|1=''H'' = (''V'', ''E'')}} और ''V'' का एक उपसमुच्चय {{mvar|V'}} दिया है,''H'' से ''V''<nowiki/>' का प्रतिबंध हाइपरग्राफ है जिसका शीर्ष ''V'' है, और ''E'' में प्रत्येक हाइपरेज {{mvar|e}} के लिए जो {{mvar|V'}} को प्रतिच्छेद करता है,इसमें एक हाइपरेज {{mvar|e'}} होता है जो ''e'' और ''V'' का प्रतिच्छेदन होता है। हाइपरग्राफ को '''संतुलित''' कहा जाता है यदि इसके सभी प्रतिबंध 2-रंगीय हैं।<ref>{{Citation|last=Berge|first=CLAUDE|title=CHAPTER 2 – Balanced Hypergraphs and Some Applications to Graph Theory|date=1973-01-01|url=http://www.sciencedirect.com/science/article/pii/B9780720422627500077|work=A Survey of Combinatorial Theory|pages=15–23|editor-last=Srivastava|editor-first=JAGDISH N.|publisher=North-Holland|language=en|isbn=978-0-7204-2262-7|access-date=2020-06-19}}</ref> एक साधारण ग्राफ द्विभाज्य है यदि यह संतुलित होता है।

एक साधारण ग्राफ द्विभाज्य है यदि इसमें कोई विषम-लंबाई चक्र नहीं है। इसी तरह, एक हाइपरग्राफ को संतुलित किया जाता है यदि इसमें कोई विषम-लंबाई वाली ''परिधि''  न हो।हाइपरग्राफ में लंबाई {{mvar|k}} की एक परिधि एक वैकल्पिक क्रम है {{math|1=(''v''{{sub|1}}, ''e''{{sub|1}}, ''v''{{sub|2}}, ''e''{{sub|2}}, …, ''v{{sub|k}}'', ''e{{sub|k}}'', ''v{{sub|k}}''{{sub|+1}} = ''v''{{sub|1}})}}, जहां {{mvar|v{{sub|i}}}} भिन्न शीर्ष हैं और {{mvar|e{{sub|i}}}} अलग-अलग हाइपरेज हैं, और प्रत्येक हाइपरेज में इसके बाईं ओर और दाईं ओर शीर्ष होता है। परिधि को असंतुलित कहा जाता है यदि प्रत्येक हाइपरेज में परिधि में कोई अन्य शीर्ष नहीं होते हैं। [[क्लॉड बर्ज]] ने सिद्ध किया कि एक हाइपरग्राफ संतुलित है अगर और केवल अगर इसमें असंतुलित विषम-लंबाई परिधि नहीं है। प्रत्येक संतुलित हाइपरग्राफ में कोनिग का गुण होता है।<ref>{{Cite journal|last1=Berge|first1=Claude|last2=Vergnas|first2=Michel LAS|date=1970|title=Sur Un Theorems Du Type König Pour Hypergraphes|journal=Annals of the New York Academy of Sciences|language=en|volume=175|issue=1|pages=32–40|doi=10.1111/j.1749-6632.1970.tb56451.x|s2cid=84670737 |issn=1749-6632}}</ref><ref name="lp" />{{Rp|468–470}}

निम्नलिखित तुल्य हैं:<ref name="lp" />{{Rp|470–471}}

* ''H'' के प्रत्येक भिन्नात्मक हाइपरग्राफ (अर्थात, कुछ हाइपरेजेज को हटाकर ''H'' से प्राप्त हाइपरग्राफ) में कोनिग गुण होता है।
* ''H'' के प्रत्येक भिन्नात्मक हाइपरग्राफ में यह गुण होता है  कि इसकी अधिकतम घात इसकी न्यूनतम [[बढ़त रंग]] संख्या के बराबर होती है।
* {{mvar|H}} में [[हेली गुण]] है, और ''H'' का प्रतिच्छेदन ग्राफ (साधारण ग्राफ जिसमें शीर्ष {{mvar|E}} और {{mvar|E}} के दो तत्व जुड़े हुए हैं और केवल यदि वे प्रतिच्छेद करते हैं) एक [[पूर्ण ग्राफ]] है।

== सुमेलन और संकुलन ==
[[ पैकिंग सेट करें | समुच्चय]] [[संकुलन]] की समस्या हाइपरग्राफ सुमेलन के तुल्य है।

एक (सरल) ग्राफ में एक शीर्षिका-संकुलन इसके शीर्षों का एक उपसमुच्चय ''P'' है, जैसे कि ''P'' में कोई भी दो शीर्ष आसन्न नहीं हैं।

ग्राफ़ में अधिकतम शीर्षिका-संकुलन खोजने की समस्या हाइपरग्राफ़ में अधिकतम सुमेलन खोजने की समस्या के तुल्य है:<ref name="lp" />{{rp|467}}

* एक हाइपरग्राफ {{math|1=''H'' = (''V'', ''E'')}} दिया है, इसके प्रतिच्छेदन ग्राफ {{math|Int(''H'')}} को सरल ग्राफ के रूप में परिभाषित करें जिसके शीर्ष {{mvar|E}} और जिनके किनारे जोड़े {{math|(''e''{{sub|1}},''e''{{sub|2}})}} हैं  जैसे कि {{math|''e''{{sub|1}}}}, {{math|''e''{{sub|2}}}} में एक शीर्ष उभयनिष्ठ है। फिर {{mvar|H}} में प्रत्येक शीर्षिका-संकुलन {{math|Int(''H'')}} में सुमेलन और विपर्येण होता है।
* एक ग्राफ {{math|1=''G'' = (''V' '', ''E' '')}} दिया गया है, इसके तारक हाइपरग्राफ {{math|St(''G'')}} को ''हाइपरग्राफ'' के रूप में परिभाषित करें जिसके शीर्ष {{mvar|E'}} हैं और जिनके हाइपरेज {{mvar|G}} के शीर्ष के तारक (स्टार) हैं (अर्थात, {{mvar|V'}} में प्रत्येक शीर्ष {{mvar|v'}} के लिए, {{math|St(''G'')}} में एक हाइपरेज होता है जिसमें  {{mvar|E'}} में वे सभी किनारे होते हैं जो ''v''' के आसन्न होते हैं)। फिर {{mvar|G}} में प्रत्येक शीर्षिका-संकुलन {{math|St(''G'')}} में सुमेलन और विपर्येण होता है।
* वैकल्पिक रूप से, एक ग्राफ {{math|1=''G'' = (''V' '', ''E' '')}} दिया गया है, इसके क्लिक हाइपरग्राफ {{math|Cl(''G'')}} को हाइपरग्राफ के रूप में परिभाषित करें, जिसके शीर्ष {{mvar|G}} के [[क्लिक्स]] हैं, और {{mvar|V'}} में  प्रत्येक शीर्ष  {{mvar|v'}} के लिए, Cl(G) में एक हाइपरेज होता है जिसमें ''G'' में सभी क्लिक्स होते हैं, जिनमें ''v''' <nowiki/>होता है। फिर से, ''G'' में प्रत्येक शीर्षिका-संकुलन {{math|Cl(''G'')}} में सुमेलन और विपर्येण होता है। ध्यान दें कि [[बहुपद समय]] में {{mvar|G}} से ''Cl(G)'' का निर्माण नहीं किया जा सकता है, इसलिए इसे एनपी-दृढ़ता सिद्ध करने के लिए समानयन के रूप में उपयोग नहीं किया जा सकता है। लेकिन इसके कुछ सैद्धांतिक उपयोग हैं।

== यह भी देखें ==
* [[3-विमीय सुमेलन]] - 3-एकसमान हाइपरग्राफ से सुमेलन करने वाले हाइपरग्राफ की एक विशेष स्थिति।
* [[हाइपरग्राफ में वर्टेक्स कवर|हाइपरग्राफ में '''<small>शीर्ष-आवरण</small>''']] 
* [[द्विदलीय हाइपरग्राफ|द्विभाज्य हाइपरग्राफ]]
* [[हाइपरग्राफ में मेघधनुष (रैन्बो) सुमेलन|हाइपरग्राफ में मेघधनुष सुमेलन]]
* [[ डी-अंतराल हाइपरग्राफ ]]- एक अनंत हाइपरग्राफ जिसमें सुमेलन और आवरक संख्या के बीच कुछ संबंध होता है।
* हाइपरग्राफ में युग्‍मानूसार गैर-असंबद्ध किनारों पर [[एर्डोस-को-राडो प्रमेय]]

== संदर्भ ==
<references />

[[Category:CS1 English-language sources (en)]]
[[Category:Created On 01/05/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:मिलान (ग्राफ सिद्धांत)]]
[[Category:हाइपरग्राफ]]