हाइपरग्राफ में मिलान: Difference between revisions

Latest revision as of 18:39, 16 May 2023

ग्राफ सिद्धांत में, हाइपरग्राफ में सुमेलन हाइपरेज का एक समुच्चय है, जिसमें हर दो हाइपरेज असंयुक्त होते हैं। यह एक ग्राफ में सुमेलन की धारणा का विस्तार है।^[1]^{: 466–470} ^[2]

परिभाषा

याद रखें कि एक हाइपरग्राफ $H$ युग्म $(V, E)$ है, जहां $V$ शीर्षों का एक समुच्चय है और $E$ के उपसमुच्चय का एक समुच्चय है जिसे $V$ हाइपरेज कहा जाता है। प्रत्येक हाइपरेज में एक या एक से अधिक शीर्ष हो सकते हैं।

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

हाइपरग्राफ H की सुमेलन संख्या $H$ में सुमेलन का सबसे बड़ा आकार है। इसे अक्सर $ν(H)$ द्वारा दर्शाया जाता है।^[1]^: 466 ^[3]

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

{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} }

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

{ {1,2,3}, {4,5,6} }

{ {1,4,5}, {2,3,6} }

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

प्रतिच्छेदी हाइपरग्राफ

एक हाइपरग्राफ $H = (V, E)$ को प्रतिच्छेदी कहा जाता है यदि E में प्रत्येक दो हाइपरेज में एक शीर्ष उभयनिष्ठ है। एक हाइपरग्राफ $H$ प्रतिच्छेद कर रहा है अगर और केवल अगर इसमें दो या दो से अधिक हाइपरेज के साथ कोई सुमेलित नहीं है, अगर और केवल अगर $ν(H) = 1$ |^[4]

एक विशेष स्थिति के रूप में एक ग्राफ में सुमेलन

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

{ {1,3}, {1,4}, {2,4} }

उपरोक्त परिभाषा के अनुसार, ग्राफ़ में सुमेलन किनारों का एक समुच्चय $M$ है, जैसे कि M में प्रत्येक दो किनारों में एक रिक्त सर्वनिष्ठ है। यह कथन तुल्य है कि M में कोई भी दो किनारे समान शीर्ष से संलग्न नहीं हैं; यह यथार्थत: एक ग्राफ़ में सुमेलन की परिभाषा है।

भिन्नात्मक सुमेलन

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

हाइपरग्राफ H की भिन्नात्मक सुमेलन संख्या $H$ में भिन्नात्मक सुमेलन का सबसे बड़ा आकार है| इसे अक्सर ν*(H) द्वारा निरूपित किया जाता है।^[3]

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

सुमेलन-संख्या( $H$ ) ≤ भिन्नात्मक -सुमेलन-संख्या ( $H$ )

प्रतीकात्मक रूप से, यह सिद्धांत लिखा गया है:

\nu (H)\leq \nu ^{*}(H)

सामान्य तौर पर, भिन्नात्मक सुमेलन संख्या सुमेलन संख्या से बड़ी हो सकती है। ज़ोल्टन फ़्यूरेडी द्वारा एक प्रमेय^[4] भिन्नात्मक-सुमेलन-संख्या (H)/ सुमेलन-संख्या(H) अनुपात पर उच्च परिबद्ध प्रदान करती है:

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

${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1+{\frac {1}{r}}.$
विशेष रूप से, एक साधारण ग्राफ में:^[5]
${\frac {\nu ^{*}(H)}{\nu (H)}}\leq {\frac {3}{2}}.$
- असमिका स्पष्ट (शार्प) है: Hr को r-एकसमान परिमित प्रक्षेपी तल होने दें। तब $ν (H r) = 1$ चूंकि प्रत्येक दो हाइपरेज एक दूसरे को प्रतिच्छेद करते हैं, और $ν*(Hr) = r – 1 + .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/r$ भिन्नात्मक सुमेलन द्वारा जो भार प्रदान करता है $1 / r$ प्रत्येक हाइपरेज के लिए (यह एक सुमेलन है क्योंकि प्रत्येक शीर्ष r हाइपरेज में सम्मिलित है,और इसका आकार $r - 1 + 1 / r$ है चूँकि वहाँ r2 - r + 1 हाइपरेज हैं)। इसलिए अनुपात यथार्थत: $r - 1 + 1 / r$ है |
यदि $r$ ऐसा है कि $r$ -एकसमान परिमित प्रक्षेपी तल उपस्थित नहीं है (उदाहरण के लिए, $r = 7$ ), तो एक प्रबल असमता रखती है:
${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$
यदि H r-विभक्त है (शीर्षों को r भागों में विभाजित किया गया है और प्रत्येक हाइपरेज में प्रत्येक भाग से एक शीर्ष सम्मिलित है), तो:
${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1.$
विशेष रूप से, द्विभाजित ग्राफ में, $ν *(H) = ν (H)$ है | यह एंड्रस ग्यारफास द्वारा सिद्ध किया गया था।^[4]
- असमिका स्पष्ट है: $H r-$ क्रम r - 1 का रुंडित प्रक्षेपी तल हो | फिर $ν (H r -) = 1$ चूंकि हर दो हाइपरेज एक दूसरे को प्रतिच्छेद करते हैं, और $ν *(H r -) = r - 1$ भिन्नात्मक सुमेलन द्वारा जो भार प्रदान करता है $1 / r$ प्रत्येक हाइपरेज के लिए ( $r 2 - r$ हाइपरेज हैं)।

पूर्ण सुमेलन

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

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

एक हाइपरग्राफ H पर विचार करें जिसमें प्रत्येक हाइपरेज में अधिकतम $n$ शीर्ष होते हैं। यदि $H$ पूर्ण भिन्नात्मक सुमेलन को प्रविष्ट करता है, तो उसकी भिन्नात्मक सुमेलन संख्या कम से कम $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}|V| ⁄n$ होती है| यदि $H$ में प्रत्येक हाइपरेज में यथार्थत: $n$ शीर्ष होते हैं, तो इसकी भिन्नात्मक सुमेलन संख्या ठीक $| V | ⁄ n$ पर होती है| ^[6] ^: sec.2 यह इस तथ्य का व्यापकीकरण है कि, किसी ग्राफ़ में, एक पूर्ण सुमेलन का आकार $| V | ⁄ 2$ है |

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

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

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

हाइपरग्राफ के लिए हॉल-टाइप प्रमेय - समीप (नैबर) के समुच्चय के आधार पर हॉल के विवाह (मेरिज) प्रमेय के अनुरूप पर्याप्त शर्तें प्रस्तुत करता है।
उच्च-घात हाइपरग्राफ में पूर्ण सुमेलन - शीर्षों की घात के आधार पर हैमिल्टोनियन चक्रों पर डिराक के प्रमेय के समान पर्याप्त शर्तें प्रस्तुत करता है।
कीवाश और माइक्रॉफ्ट ने हाइपरग्राफ सुमेलन के लिए एक ज्यामितीय सिद्धांत विकसित किया।^[7]

संतुलित समुच्चय-परिवार

ग्राउंड समुच्चय $V$ पर एक समुच्चय-परिवार E को कहा जाता है ( $V$ के संबंध में ) अगर हाइपरग्राफ $H = (V, E)$ पूर्ण भिन्नात्मक सुमेलन मान लेता है।^[6] ^: sec.2

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

अधिकतम सुमेलन की गणना

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

सुमेलन और आवरण

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

हाइपरग्राफ $H$ की शीर्ष-आवरण संख्या का सबसे छोटा आकार है। तिर्यक रेखा के लिए इसे अक्सर $τ (H)$ ,^[1]^: 466 से दर्शाया जाता है।

एक भिन्नात्मक शीर्ष-आवरण एक ऐसा फलन है जो V में प्रत्येक शीर्ष को भार नियत करता है, जैसे कि E में प्रत्येक हाइपरेज $e$ के लिए, e में शीर्षों के भिन्नों का योग कम से कम 1 है। शीर्ष-आवरण एक भिन्नात्मक शीर्ष-आवरण की एक विशेष स्थिति है जिसमें सभी भार या तो 0 या 1 हैं। भिन्नात्मक शीर्ष-आवरण का आकार सभी शीर्षों के भिन्नों का योग होता है।

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

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

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

भिन्नात्मक-सुमेलन-संख्या (H) = भिन्नात्मक-शीर्ष-आवरण- संख्या (H)।^[4]

इसलिए, हर हाइपरग्राफ H के लिए:: $\nu (H)\leq \nu ^{*}(H)=\tau ^{*}(H)\leq \tau (H)$

यदि $H$ में हाइपरेज का आकार अधिकतम r है, तो अधिकतम सुमेलन में सभी हाइपरेज का सम्मिलन एक शीर्ष-आवरण है (यदि कोई विवृत हाइपरेज था, तो हम इसे सुमेलन में जोड़ सकते थे)। इसलिए:

\tau (H)\leq r\cdot \nu (H).

यह असमता ठोस (टाइट) है: समता रखती है, उदाहरण के लिए, जब $V$ में $r \cdot ν (H) + r - 1$ शीर्ष होते हैं और $E$ में $r$ शीर्षों के सभी उपसमुच्चय होते हैं।

हालाँकि, सामान्य रूप से $τ *(H) < r \cdot ν (H)$ , चूँकि $ν *(H) < r \cdot ν (H)$ ; ऊपर भिन्नात्मक सुमेलन देखें।

रायसर का अनुमानित कथन कहता है कि, प्रत्येक $r$ -विभक्त $r$ -एकसमान में:

\tau (H)\leq (r-1)\nu (H).

अनुमानित कथन की कुछ विशेष स्थिति सिद्ध हुई हैं; रायसर का अनुमानित कथन देखें।

कोनिग के गुण

एक हाइपरग्राफ में कोनिग के गुण होते है यदि इसकी अधिकतम सुमेलन संख्या इसकी न्यूनतम शीर्ष-आवरण संख्या के तुल्य होती है, अर्थात् यदि $ν (H) = τ (H)$ |कोनिग-एगेर्वरी प्रमेय से पता चलता है कि प्रत्येक द्विभाज्य ग्राफ में कोनिग गुण होता है। इस प्रमेय को हाइपरग्राफ तक विस्तारित करने के लिए, हमें द्विभाज्यता की धारणा को हाइपरग्राफ तक विस्तारित करने की आवश्यकता होती है।^[1]^: 468

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

एक प्रबल व्यापकीकरण इस प्रकार है। एक हाइपरग्राफ $H = (V, E)$ और V का एक उपसमुच्चय $V'$ दिया है,H से V' का प्रतिबंध हाइपरग्राफ है जिसका शीर्ष V है, और E में प्रत्येक हाइपरेज $e$ के लिए जो $V'$ को प्रतिच्छेद करता है,इसमें एक हाइपरेज $e'$ होता है जो e और V का प्रतिच्छेदन होता है। हाइपरग्राफ को संतुलित कहा जाता है यदि इसके सभी प्रतिबंध 2-रंगीय हैं।^[8] एक साधारण ग्राफ द्विभाज्य है यदि यह संतुलित होता है।

एक साधारण ग्राफ द्विभाज्य है यदि इसमें कोई विषम-लंबाई चक्र नहीं है। इसी तरह, एक हाइपरग्राफ को संतुलित किया जाता है यदि इसमें कोई विषम-लंबाई वाली परिधि न हो।हाइपरग्राफ में लंबाई $k$ की एक परिधि एक वैकल्पिक क्रम है $(v 1, e 1, v 2, e 2, \dots, v k, e k, v k +1 = v 1)$ , जहां $v i$ भिन्न शीर्ष हैं और $e i$ अलग-अलग हाइपरेज हैं, और प्रत्येक हाइपरेज में इसके बाईं ओर और दाईं ओर शीर्ष होता है। परिधि को असंतुलित कहा जाता है यदि प्रत्येक हाइपरेज में परिधि में कोई अन्य शीर्ष नहीं होते हैं। क्लॉड बर्ज ने सिद्ध किया कि एक हाइपरग्राफ संतुलित है अगर और केवल अगर इसमें असंतुलित विषम-लंबाई परिधि नहीं है। प्रत्येक संतुलित हाइपरग्राफ में कोनिग का गुण होता है।^[9]^[1]^{: 468–470}

निम्नलिखित तुल्य हैं:^[1]^{: 470–471}

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

सुमेलन और संकुलन

समुच्चय संकुलन की समस्या हाइपरग्राफ सुमेलन के तुल्य है।

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

ग्राफ़ में अधिकतम शीर्षिका-संकुलन खोजने की समस्या हाइपरग्राफ़ में अधिकतम सुमेलन खोजने की समस्या के तुल्य है:^[1]^: 467

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

यह भी देखें

3-विमीय सुमेलन - 3-एकसमान हाइपरग्राफ से सुमेलन करने वाले हाइपरग्राफ की एक विशेष स्थिति।
हाइपरग्राफ में शीर्ष-आवरण
द्विभाज्य हाइपरग्राफ
हाइपरग्राफ में मेघधनुष सुमेलन
डी-अंतराल हाइपरग्राफ - एक अनंत हाइपरग्राफ जिसमें सुमेलन और आवरक संख्या के बीच कुछ संबंध होता है।
हाइपरग्राफ में युग्‍मानूसार गैर-असंबद्ध किनारों पर एर्डोस-को-राडो प्रमेय

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
↑ Berge, Claude (1973). रेखांकन और हाइपरग्राफ. Amsterdam: North-Holland.
↑ ^3.0 ^3.1 Aharoni, Ron; Kessler, Ofra (1990-10-15). "द्विदलीय हाइपरग्राफ के लिए हॉल के प्रमेय के संभावित विस्तार पर". Discrete Mathematics (in English). 84 (3): 309–313. doi:10.1016/0012-365X(90)90136-6. ISSN 0012-365X.
↑ ^4.0 ^4.1 ^4.2 ^4.3 Füredi, Zoltán (1981-06-01). "समान हाइपरग्राफ में अधिकतम डिग्री और आंशिक मिलान". Combinatorica (in English). 1 (2): 155–162. doi:10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.
↑ Lovász, L. (1974). Berge, Claude; Ray-Chaudhuri, Dijen (eds.). "हाइपरग्राफ के लिए मिनिमैक्स प्रमेय". Hypergraph Seminar. Lecture Notes in Mathematics (in English). Berlin, Heidelberg: Springer. 411: 111–126. doi:10.1007/BFb0066186. ISBN 978-3-540-37803-7.
↑ ^6.0 ^6.1 Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-01-02). "कई टुकड़ों के साथ उचित विभाजन". Discrete Applied Mathematics (in English). 283: 115–122. arXiv:1710.09477. doi:10.1016/j.dam.2019.12.018. ISSN 0166-218X. S2CID 119602376.
↑ Keevash, Peter; Mycroft, Richard (2015-01-01). हाइपरग्राफ मिलान के लिए एक ज्यामितीय सिद्धांत. Memoirs of the American Mathematical Society (in English). Vol. 233. American Mathematical Society. ISBN 978-1-4704-0965-4.
↑ Berge, CLAUDE (1973-01-01), Srivastava, JAGDISH N. (ed.), "CHAPTER 2 – Balanced Hypergraphs and Some Applications to Graph Theory", A Survey of Combinatorial Theory (in English), North-Holland, pp. 15–23, ISBN 978-0-7204-2262-7, retrieved 2020-06-19
↑ Berge, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes". Annals of the New York Academy of Sciences (in English). 175 (1): 32–40. doi:10.1111/j.1749-6632.1970.tb56451.x. ISSN 1749-6632. S2CID 84670737.

[lp-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549

[2] Berge, Claude (1973). रेखांकन और हाइपरग्राफ. Amsterdam: North-Holland.

[:1-3] 3.0 ^3.1 Aharoni, Ron; Kessler, Ofra (1990-10-15). "द्विदलीय हाइपरग्राफ के लिए हॉल के प्रमेय के संभावित विस्तार पर". Discrete Mathematics (in English). 84 (3): 309–313. doi:10.1016/0012-365X(90)90136-6. ISSN 0012-365X.

[:2-4] 4.0 ^4.1 ^4.2 ^4.3 Füredi, Zoltán (1981-06-01). "समान हाइपरग्राफ में अधिकतम डिग्री और आंशिक मिलान". Combinatorica (in English). 1 (2): 155–162. doi:10.1007/BF02579271. ISSN 1439-6912. S2CID 10530732.

[5] Lovász, L. (1974). Berge, Claude; Ray-Chaudhuri, Dijen (eds.). "हाइपरग्राफ के लिए मिनिमैक्स प्रमेय". Hypergraph Seminar. Lecture Notes in Mathematics (in English). Berlin, Heidelberg: Springer. 411: 111–126. doi:10.1007/BFb0066186. ISBN 978-3-540-37803-7.

[:0-6] 6.0 ^6.1 Nyman, Kathryn; Su, Francis Edward; Zerbib, Shira (2020-01-02). "कई टुकड़ों के साथ उचित विभाजन". Discrete Applied Mathematics (in English). 283: 115–122. arXiv:1710.09477. doi:10.1016/j.dam.2019.12.018. ISSN 0166-218X. S2CID 119602376.

[7] Keevash, Peter; Mycroft, Richard (2015-01-01). हाइपरग्राफ मिलान के लिए एक ज्यामितीय सिद्धांत. Memoirs of the American Mathematical Society (in English). Vol. 233. American Mathematical Society. ISBN 978-1-4704-0965-4.

[8] Berge, CLAUDE (1973-01-01), Srivastava, JAGDISH N. (ed.), "CHAPTER 2 – Balanced Hypergraphs and Some Applications to Graph Theory", A Survey of Combinatorial Theory (in English), North-Holland, pp. 15–23, ISBN 978-0-7204-2262-7, retrieved 2020-06-19

[9] Berge, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes". Annals of the New York Academy of Sciences (in English). 175 (1): 32–40. doi:10.1111/j.1749-6632.1970.tb56451.x. ISSN 1749-6632. S2CID 84670737.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

@@ Line 1: / Line 1: @@
 {{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>
+[[ग्राफ सिद्धांत]] में, [[ 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>
@@ Line 7: / Line 7: @@
 याद रखें कि एक [[हाइपरग्राफ]] {{mvar|H}} युग्म {{math|(''V'', ''E'')}} है, जहां {{mvar|V}} शीर्षों का एक [[सेट (गणित)|समुच्चय]] है और {{mvar|E}} के [[उपसमुच्चय]] का एक समुच्चय है जिसे {{mvar|V}} ''हाइपरेज'' कहा जाता है। प्रत्येक हाइपरेज में एक या एक से अधिक शीर्ष हो सकते हैं।
-एक 'मिलान' में {{mvar|H}} एक उपसमुच्चय है {{mvar|M}} का {{mvar|E}}, ऐसा है कि हर दो hyperedges {{math|''e''{{sub|1}}}} और {{math|''e''{{sub|2}}}} में {{mvar|M}} में एक खाली चौराहा है (कोई शीर्ष समान नहीं है)।
+''H'' में '''सुमेलन''' , ''E'' का एक उपसमुच्चय {{mvar|M}} है, जैसे कि ''M'' में प्रत्येक दो हाइपरेज e1 और e2 में एक रिक्त सर्वनिष्ठ है (कोई शीर्ष उभयनिष्ठ नहीं है)।
-हाइपरग्राफ की मिलान संख्या {{mvar|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>
+हाइपरग्राफ ''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}} समुच्चयहो {{math|{1,2,3,4,5,6,7}.}} एक 3-समान हाइपरग्राफ पर विचार करें {{mvar|V}} (एक हाइपरग्राफ जिसमें प्रत्येक हाइपरेज में ठीक 3 कोने होते हैं)। होने देना {{mvar|H}} 4 हाइपरेज के साथ 3-समान हाइपरग्राफ बनें:
+उदाहरण के लिए, {{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 के कई मेलों को स्वीकार करता है, उदाहरण के लिए:
+तब {{mvar|H}} आकार 2 के कई सुमेलनों को सम्मिलित करता है, उदाहरण के लिए:
 : {{math|{ {1,2,3}, {4,5,6} } }}
 : {{math|{ {1,4,5}, {2,3,6} } }}
-हालाँकि, 3 हाइपरएज के किसी भी उपसमुच्चय में, उनमें से कम से कम दो प्रतिच्छेद करते हैं, इसलिए आकार 3 का कोई मेल नहीं है। इसलिए, मिलान संख्या {{mvar|H}}2 है।
+हालाँकि, 3 हाइपरेज के किसी भी उपसमुच्चय में, उनमें से कम से कम दो प्रतिच्छेद करते हैं, इसलिए आकार 3 का कोई सुमेल नहीं है। इसलिए, H की सुमेलन संख्या 2 है।
-== इंटरसेक्टिंग हाइपरग्राफ{{Anchor|intersecting}} ==
+== प्रतिच्छेदी हाइपरग्राफ{{Anchor|intersecting}} ==
-एक हाइपरग्राफ {{math|1=''H'' = (''V'', ''E'')}} को इंटरसेक्टिंग कहा जाता है अगर हर दो हाइपरेज इन {{mvar|E}} में एक शीर्ष उभयनिष्ठ है। एक हाइपरग्राफ {{mvar|H}} प्रतिच्छेद कर रहा है [[अगर और केवल अगर]] इसमें दो या दो से अधिक हाइपरेज के साथ कोई मेल नहीं है, अगर और केवल अगर {{math|1=ν(''H'') = 1}}.<ref name=":2" />
+एक हाइपरग्राफ {{math|1=''H'' = (''V'', ''E'')}} को प्रतिच्छेदी कहा जाता है यदि ''E'' में प्रत्येक दो हाइपरेज में एक शीर्ष उभयनिष्ठ है। एक हाइपरग्राफ {{mvar|H}} प्रतिच्छेद कर रहा है [[अगर और केवल अगर]] इसमें दो या दो से अधिक हाइपरेज के साथ कोई सुमेलित नहीं है, अगर और केवल अगर {{math|1=ν(''H'') = 1}}|<ref name=":2" />
-== एक विशेष मामले के रूप में एक ग्राफ में मिलान ==
+== एक विशेष स्थिति के रूप में एक ग्राफ में सुमेलन ==
-[[आत्म पाश]] के बिना एक ग्राफ केवल 2-समान हाइपरग्राफ है: प्रत्येक किनारे को दो कोने के समुच्चयके रूप में माना जा सकता है जो इसे जोड़ता है। उदाहरण के लिए, यह 2-समान हाइपरग्राफ 4 कोने वाले ग्राफ़ का प्रतिनिधित्व करता है {{math|{1,2,3,4} }} और 3 किनारे:
+[[आत्म पाश|स्वपाश]] के बिना एक ग्राफ केवल 2-एकसमान हाइपरग्राफ है: प्रत्येक किनारे को दो शीर्षों के समुच्चय के रूप में माना जा सकता है जो इसे जोड़ता है। उदाहरण के लिए, यह 2-एकसमान हाइपरग्राफ 4 शीर्षों {1,2,3,4} और 3 किनारों के साथ एक ग्राफ को प्रस्तुत करता है:
 : {{math|{ {1,3}, {1,4}, {2,4} } }}
-उपरोक्त परिभाषा के अनुसार, ग्राफ़ में मिलान एक समुच्चयहै {{mvar|M}} किनारों की, जैसे कि प्रत्येक दो किनारों में {{mvar|M}} एक खाली चौराहा है। यह कहने के बराबर है कि कोई भी दो किनारे अंदर नहीं हैं {{mvar|M}} एक ही शीर्ष के निकट हैं; यह बिल्कुल मिलान (ग्राफ सिद्धांत) की परिभाषा है।
+उपरोक्त परिभाषा के अनुसार, ग्राफ़ में सुमेलन किनारों का एक समुच्चय {{mvar|M}}  है, जैसे कि ''M'' में प्रत्येक दो किनारों में एक रिक्त सर्वनिष्ठ है। यह कथन तुल्य है कि ''M'' में कोई भी दो किनारे समान शीर्ष से संलग्न नहीं हैं;  यह यथार्थत: एक [[ग्राफ़ में सुमेलन]] की परिभाषा है।
-== [[आंशिक मिलान]] ==
+== [[आंशिक मिलान|भिन्नात्मक सुमेलन]] ==
-हाइपरग्राफ में एक भिन्नात्मक मिलान एक ऐसा कार्य है जो एक भिन्न को निर्दिष्ट करता है {{math|[0,1]}} प्रत्येक हाइपरएज के लिए, जैसे कि प्रत्येक शीर्ष के लिए {{mvar|v}} में {{mvar|V}}, युक्त hyperedges के अंशों का योग {{mvar|v}} अधिक से अधिक 1 है। एक मिलान भिन्नात्मक मिलान का एक विशेष मामला है जिसमें सभी अंश या तो 0 या 1 हैं। एक भिन्नात्मक मिलान का आकार सभी हाइपरेज के अंशों का योग है।
+हाइपरग्राफ में एक [[भिन्नात्मक सुमेलन|'''भिन्नात्मक सुमेलन''']] एक ऐसा फलन है जो प्रत्येक हाइपरेज को [0,1] में एक भिन्न प्रदान करता है, जैसे कि ''V'' में प्रत्येक शीर्ष {{mvar|v}} के लिए, ''v'' वाले हाइपरेज के भिन्नों का योग अधिकतम 1 है। एक सुमेलन भिन्नात्मक सुमेलन की एक विशेष स्थिति है जिसमें सभी भिन्न या तो 0 या 1 होते हैं। भिन्नात्मक सुमेलन का आकार सभी हाइपरेज के भिन्नों का योग होता है।
-हाइपरग्राफ की 'आंशिक मिलान संख्या' {{mvar|H}} भिन्नात्मक मिलान का सबसे बड़ा आकार है {{mvar|H}}. इसे अक्सर द्वारा निरूपित किया जाता है {{math|''ν''*(''H'')}}.<ref name=":1" />
+हाइपरग्राफ ''H'' की '''भिन्नात्मक सुमेलन संख्या''' {{mvar|H}} में भिन्नात्मक सुमेलन का सबसे बड़ा आकार है| इसे अक्सर ''ν*(H)'' द्वारा निरूपित किया जाता है।<ref name=":1" />
-चूंकि मिलान प्रत्येक हाइपरग्राफ के लिए आंशिक मिलान का एक विशेष मामला है {{mvar|H}}: <blockquote>मिलान-संख्या({{mvar|H}}) ≤ आंशिक-मिलान-संख्या ({{mvar|H}})</blockquote>
+चूंकि सुमेलन प्रत्येक हाइपरग्राफ ''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> आंशिक-मिलान पर ऊपरी सीमा प्रदान करता है-{{nowrap|number({{mvar|H}}) / matching-}}संख्या({{mvar|H}}) अनुपात:
+सामान्य तौर पर, भिन्नात्मक सुमेलन संख्या सुमेलन संख्या से बड़ी हो सकती है। ज़ोल्टन फ़्यूरेडी द्वारा एक प्रमेय<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|H}} अधिक से अधिक शामिल हैं {{mvar|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>
+शीर्षों का एक समुच्चय {{mvar|V}}  दिया गया है, ''V'' के उपसमुच्चय का एक संग्रह {{mvar|E}} संतुलित कहा जाता है अगर हाइपरग्राफ {{math|(''V'',''E'')}} एक पूर्ण भिन्नात्मक सुमेलन स्वीकार करता है।
-** असमानता तेज है: चलो {{mvar|H{{sub|r}}}} हो {{mvar|r}}-समान परिमित प्रक्षेपी तल। तब  {{math|1=''ν''(''H''{{sub|''r''}}) = 1}} चूंकि हर दो हाइपरेज एक दूसरे को काटते हैं, और {{math|1=''ν''*(''H''{{sub|''r''}}) = ''r'' – 1 + {{sfrac|1|''r''}}}} भिन्नात्मक मिलान द्वारा जो भार प्रदान करता है {{math|{{sfrac|1|''r''}}}} प्रत्येक हाइपरेज के लिए (यह एक मिलान है क्योंकि प्रत्येक वर्टेक्स में निहित है {{mvar|r}} हाइपरएजेज, और इसका आकार है {{math|''r'' – 1 + {{sfrac|1|''r''}}}} क्योंकि वहां हैं {{math|''r''{{sup|2}} – ''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}}-पार्टिट (कोने में विभाजित हैं {{mvar|r}} भागों और प्रत्येक हाइपरेज में प्रत्येक भाग से एक शीर्ष होता है), फिर: <p><math>\frac{\nu^*(H)}{\nu (H)} \leq r-1.</math></p><p>विशेष रूप से, द्विदलीय ग्राफ में, {{math|1=''ν''*(''H'') = ''ν''(''H'')}}. यह András Gyárfás द्वारा सिद्ध किया गया था।<ref name=":2" /></p>
-** असमानता तेज है: चलो {{mvar|H{{sub|r-}}}} ऑर्डर का [[छोटा प्रोजेक्टिव प्लेन]] हो {{math|''r'' – 1}}. तब {{math|1=''ν''(''H''{{sub|''r''-}}) = 1}} चूंकि हर दो हाइपरेज एक दूसरे को काटते हैं, और {{math|1=''ν''*(''H''{{sub|''r''-}}) = ''r'' – 1}} भिन्नात्मक मिलान द्वारा जो भार प्रदान करता है {{math|{{sfrac|1|''r''}}}} प्रत्येक हाइपरेज के लिए (वहाँ हैं {{math|''r''{{sup|2}} – ''r''}} हाइपरएज)।
-== सटीक मिलान ==
+उदाहरण के लिए, अगर {{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 }.}}
-एक मिलान {{mvar|M}} को पूर्ण कहा जाता है यदि प्रत्येक शीर्ष {{mvar|v}} में {{mvar|V}} ठीक एक हाइपरएज में समाहित है {{mvar|M}}. यह एक ग्राफ में पूर्ण मिलान की धारणा का स्वाभाविक विस्तार है।
-एक भिन्नात्मक मिलान {{mvar|M}प्रत्येक शीर्ष के लिए } को उत्तम कहा जाता है {{mvar|v}} में {{mvar|V}}, में hyperedges के अंशों का योग {{mvar|M}} युक्त {{mvar|v}} ठीक 1 है।
+हाइपरग्राफ में एक पूर्ण सुमेलन के अस्तित्व के लिए विभिन्न पर्याप्त शर्तें हैं:
-हाइपरग्राफ पर विचार करें {{mvar|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}}}}.
+* [[हाइपरग्राफ के लिए हॉल-टाइप प्रमेय]] - समीप (नैबर) के समुच्चय के आधार पर हॉल के विवाह (मेरिज) प्रमेय के अनुरूप पर्याप्त शर्तें प्रस्तुत करता है।
+* [[हाई-डिग्री हाइपरग्राफ में सटीक मिलान|उच्च-घात हाइपरग्राफ में]] [[पूर्ण सुमेलन]] - शीर्षों की घात के आधार पर [[हैमिल्टोनियन चक्रों पर डिराक के प्रमेय]] के समान पर्याप्त शर्तें प्रस्तुत करता है।
+* [[पीटर कीवाश|कीवाश]] और माइक्रॉफ्ट ने हाइपरग्राफ सुमेलन के लिए एक ज्यामितीय सिद्धांत विकसित किया।<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}} शिखरों का, एक संग्रह {{mvar|E}} के उपसमुच्चय {{mvar|V}} संतुलित कहा जाता है अगर हाइपरग्राफ {{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 }.}}
+== संतुलित समुच्चय-परिवार ==
+ग्राउंड समुच्चय {{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-एकसमान) ग्राफ़ की स्थिति के विपरीत है जिसमें बहुपद समय में [[अधिकतम-गणनांक सुमेलन]] की गणना की जा सकती है।
-* [[पीटर कीवाश]] और माइक्रॉफ्ट ने हाइपरग्राफ मिलान के लिए एक ज्यामितीय सिद्धांत विकसित किया।<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>
+== सुमेलन और आवरण ==
+[[हाइपरग्राफ|''हाइपरग्राफ'']] {{math|1=''H'' = (''V'', ''E'')}} में एक [[शीर्ष-आवरण|''शीर्ष-आवरण'']] ''V'' का एक उपसमुच्चय ''T'' है, जैसे कि प्रत्येक हाइपरेज में ''T'' का कम से कम एक शीर्ष होता है {{mvar|T}} (इसे [[अनुप्रस्थ]] या [[हिटिंग सेट|आघाती]] [[समुच्चय]] भी कहा जाता है, और यह समुच्चय आवरण के तुल्य है)। यह एक ग्राफ में ''[[वर्टेक्स कवर|शीर्ष-आवरण]]''  की धारणा का व्यापकीकरण है।
-== संतुलित सेट-फ़ैमिली ==
+हाइपरग्राफ {{mvar|H}} की '''शीर्ष-आवरण संख्या''' का सबसे छोटा आकार है। तिर्यक रेखा के लिए इसे अक्सर {{math|''τ''(''H'')}},<ref name="lp" />{{rp|466}}  से दर्शाया जाता है।
-[[सेट का परिवार|समुच्चयका परिवार]] | सेट-परिवार {{mvar|E}} ग्राउंड समुच्चयपर {{mvar|V}} को संतुलित कहा जाता है (के संबंध में {{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}.}} {{mvar|E}} संतुलित है, क्योंकि वजन के साथ एक पूर्ण आंशिक मिलान होता है {{math|{1/2, 1/2, 1/2, 1/2, 1}.}}
+एक '''भिन्नात्मक''' <small>'''शीर्ष-आवरण'''</small> एक ऐसा फलन है जो ''V'' में प्रत्येक शीर्ष को भार नियत करता है, जैसे कि ''E'' में प्रत्येक  हाइपरेज {{mvar|e}} के लिए, ''e'' में शीर्षों के भिन्नों का योग कम से कम 1 है। शीर्ष-आवरण एक भिन्नात्मक शीर्ष-आवरण की एक विशेष स्थिति है जिसमें सभी भार या तो 0 या 1 हैं। भिन्नात्मक शीर्ष-आवरण का आकार सभी शीर्षों के भिन्नों का योग होता है।
-== अधिकतम मिलान की गणना ==
+हाइपरग्राफ {{mvar|H}} की '''शीर्ष-आवरण संख्या''' ''H'' में एक भिन्नात्मक शीर्ष-आवरण का सबसे छोटा आकार है। इसे अक्सर {{math|''τ''*(''H'')}} से दर्शाया जाता है।
-हाइपरग्राफ में अधिकतम-कार्डिनैलिटी मिलान खोजने की समस्या, इस प्रकार गणना करना <math>\nu(H)</math>, 3-समान हाइपरग्राफ के लिए भी एनपी-हार्ड है ([[3-आयामी मिलान]] देखें)। यह सरल (2-समान) ग्राफ़ के मामले के विपरीत है जिसमें [[अधिकतम कार्डिनैलिटी मिलान]]|मैक्सिमम-कार्डिनैलिटी मैचिंग की गणना बहुपद समय में की जा सकती है।
-== मिलाना और ढकना ==
+चूँकि प्रत्येक हाइपरग्राफ ''H'' के लिए शीर्ष-आवरण एक भिन्नात्मक शीर्ष-आवरण की एक विशेष स्थिति है:
-हाइपरग्राफ में वर्टेक्स कवर | हाइपरग्राफ में वर्टेक्स-कवर {{math|1=''H'' = (''V'', ''E'')}} एक उपसमुच्चय है {{mvar|T}} का {{mvar|V}}, जैसे कि हर हाइपरेज इन {{mvar|E}} में कम से कम एक शीर्ष शामिल है {{mvar|T}} (इसे ट्रांसवर्सल (कॉम्बिनेटरिक्स) या [[हिटिंग सेट|हिटिंग]] समुच्चयभी कहा जाता है, और यह समुच्चयकवर समस्या के बराबर है)। यह एक ग्राफ में [[वर्टेक्स कवर]] की धारणा का सामान्यीकरण है।
-हाइपरग्राफ का वर्टेक्स-कवर नंबर {{mvar|H}} वर्टेक्स कवर का सबसे छोटा आकार है {{mvar|H}}. इसे अक्सर द्वारा निरूपित किया जाता है {{math|''τ''(''H'')}},<ref name="lp" />{{rp|466}} अनुप्रस्थ के लिए।
+रैखिक प्रोग्रामन द्वैत का तात्पर्य है कि, प्रत्येक हाइपरग्राफ H के लिए:
-एक फ्रैक्शनल वर्टेक्स-कवर एक ऐसा फंक्शन है जो प्रत्येक वर्टेक्स को वेट असाइन करता है {{mvar|V}}, जैसे कि हर हाइपरेज के लिए {{mvar|e}} में {{mvar|E}}, में शीर्षों के अंशों का योग {{mvar|e}} कम से कम 1 है। एक वर्टेक्स कवर एक भिन्नात्मक वर्टेक्स कवर का एक विशेष मामला है जिसमें सभी वज़न या तो 0 या 1 हैं। एक भिन्नात्मक वर्टेक्स-कवर का आकार सभी वर्टिकल के अंशों का योग है।
+भिन्नात्मक-सुमेलन-संख्या (''H'') = भिन्नात्मक-शीर्ष-आवरण- संख्या (''H'')।<ref name=":2" />
-हाइपरग्राफ का 'फ्रैक्शनल वर्टेक्स-कवर नंबर' {{mvar|H}} भिन्नात्मक वर्टेक्स-आवरण का सबसे छोटा आकार है {{mvar|H}}. इसे अक्सर द्वारा निरूपित किया जाता है {{math|''τ''*(''H'')}}.
+इसलिए, हर हाइपरग्राफ H के लिए::<math>\nu(H) \leq \nu^*(H) =  \tau^*(H)\leq  \tau(H) </math>
-चूँकि हर हाइपरग्राफ के लिए वर्टेक्स-कवर एक भिन्नात्मक वर्टेक्स-कवर का एक विशेष मामला है {{mvar|H}}:
+यदि {{mvar|H}} में हाइपरेज का आकार अधिकतम ''r'' है, तो अधिकतम सुमेलन में सभी हाइपरेज का सम्मिलन एक शीर्ष-आवरण है (यदि कोई विवृत हाइपरेज था, तो हम इसे सुमेलन में जोड़ सकते थे)। इसलिए:
-<ब्लॉककोट>फ्रैक्शनल-वर्टेक्स-कवर-नंबर ({{mvar|H}}) ≤ वर्टेक्स-कवर-संख्या ({{mvar|H}}). </ब्लॉककोट>
-रैखिक प्रोग्रामिंग द्वैत का तात्पर्य है कि, प्रत्येक हाइपरग्राफ के लिए {{mvar|H}}:
-<ब्लॉककोट>फ्रैक्शनल-मैचिंग-नंबर ({{mvar|H}}) = आंशिक-वर्टेक्स-कवर-नंबर ({{mvar|H}}). </ब्लॉककोट>
-इसलिए, हर हाइपरग्राफ के लिए {{mvar|H}}:<ref name=":2" />:<math>\nu(H) \leq \nu^*(H) =  \tau^*(H)\leq  \tau(H) </math>
-यदि प्रत्येक हाइपरेज का आकार {{mvar|H}} ज्यादा से ज्यादा है {{mvar|r}} तो अधिकतम मिलान में सभी हाइपरेज का मिलन एक वर्टेक्स-कवर है (यदि कोई खुला हाइपरेज था, तो हम इसे मिलान में जोड़ सकते थे)। इसलिए:
 :<math>\tau(H)\leq r\cdot \nu(H).</math>
-यह असमानता तंग है: समानता रखती है, उदाहरण के लिए, कब {{mvar|V}}  रोकना  {{math|''r''⋅''ν''(''H'') + ''r'' – 1}} शिखर और {{mvar|E}} के सभी उपसमुच्चय शामिल हैं {{mvar|r}} शिखर।
+यह असमता ठोस (टाइट) है: समता रखती है, उदाहरण के लिए, जब {{mvar|V}}  में {{math|''r''⋅''ν''(''H'') + ''r'' – 1}} शीर्ष होते हैं और {{mvar|E}} में {{mvar|r}} शीर्षों के सभी उपसमुच्चय होते हैं।
-हालाँकि, सामान्य तौर पर {{math|''τ''*(''H'') <  ''r''⋅''ν''(''H'')}}, तब से {{math|''ν''*(''H'') < ''r''⋅''ν''(''H'')}}; हाइपरग्राफ में मिलान देखें#ऊपर भिन्नात्मक मिलान।
+हालाँकि, सामान्य रूप से {{math|''τ''*(''H'') <  ''r''⋅''ν''(''H'')}}, चूँकि  {{math|''ν''*(''H'') < ''r''⋅''ν''(''H'')}}; ऊपर [[भिन्नात्मक सुमेलन]] देखें।
-रायसर का अनुमान कहता है कि, प्रत्येक में {{mvar|r}}-मैच {{mvar|r}}-समान हाइपरग्राफ:
+[[रायसर का अनुमान|रायसर का अनुमानित कथन]] कहता है कि, प्रत्येक {{mvar|r}}-विभक्त {{mvar|r}}-एकसमान में:
 :<math>\tau (H)\leq (r-1) \nu(H).</math>
-अनुमान के कुछ विशेष मामले सिद्ध हुए हैं; रायसर का अनुमान देखें।
+अनुमानित कथन की कुछ विशेष स्थिति सिद्ध हुई हैं; [[रायसर का अनुमानित कथन]] देखें।
-== कोनिग की संपत्ति ==
+== कोनिग के गुण ==
-एक हाइपरग्राफ में कोनिग संपत्ति होती है यदि इसकी अधिकतम मिलान संख्या इसकी न्यूनतम वर्टेक्स-कवर संख्या के बराबर होती है, अर्थात् यदि {{math|1=''ν''(''H'') = ''τ''(''H'')}}. कोनिग की प्रमेय (ग्राफ सिद्धांत) | कोनिग-एगेर्वरी प्रमेय से पता चलता है कि प्रत्येक द्विदलीय ग्राफ में कोनिग गुण होता है। इस प्रमेय को हाइपरग्राफ तक विस्तारित करने के लिए, हमें द्विदलीयता की धारणा को हाइपरग्राफ तक विस्तारित करने की आवश्यकता है।<ref name="lp" />{{rp|468}}
+एक हाइपरग्राफ में '''कोनिग के गुण''' होते है यदि इसकी अधिकतम सुमेलन संख्या इसकी न्यूनतम शीर्ष-आवरण संख्या के तुल्य होती है, अर्थात् यदि {{math|1=''ν''(''H'') = ''τ''(''H'')}} |[[कोनिग-एगेर्वरी प्रमेय]] से पता चलता है कि प्रत्येक [[द्विभाज्य ग्राफ]] में कोनिग गुण होता है। इस प्रमेय को हाइपरग्राफ तक विस्तारित करने के लिए, हमें द्विभाज्यता की धारणा को हाइपरग्राफ तक विस्तारित करने की आवश्यकता होती है।<ref name="lp" />{{rp|468}}
-एक प्राकृतिक सामान्यीकरण इस प्रकार है। एक हाइपरग्राफ को 2-रंगीन कहा जाता है यदि इसके कोने 2-रंग के हो सकते हैं ताकि प्रत्येक हाइपरेज (आकार कम से कम 2) में प्रत्येक रंग का कम से कम एक शीर्ष हो। एक वैकल्पिक शब्द [[संपत्ति बी]] है। एक साधारण ग्राफ द्विपक्षीय है अगर यह 2-रंगीन है। हालांकि, कोनिग की संपत्ति के बिना 2-रंगीन हाइपरग्राफ हैं। उदाहरण के लिए, हाइपरग्राफ पर विचार करें {{math|1=''V'' = {1,2,3,4} }} सभी ट्रिपल के साथ {{math|1=''E'' = { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }.}} यह 2-रंगीन है, उदाहरण के लिए, हम रंग सकते हैं {{math|{1,2} }} नीला और {{math|{3,4} }} सफ़ेद। हालाँकि, इसकी मिलान संख्या 1 है और इसका वर्टेक्स-कवर नंबर 2 है।
+एक साधारण व्यापकीकरण इस प्रकार है। एक हाइपरग्राफ को '''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'')}} और एक उपसमुच्चय {{mvar|V'}} का {{mvar|V}}, का प्रतिबंध {{mvar|H}} को {{mvar|V'}} वह हाइपरग्राफ है जिसके शीर्ष हैं {{mvar|V}}, और हर हाइपरएज के लिए {{mvar|e}} में {{mvar|E}} जो प्रतिच्छेद करता है {{mvar|V'}}, इसमें हाइपरएज है {{mvar|e'}} वह चौराहा है {{mvar|e}} और {{mvar|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> एक साधारण ग्राफ द्विदलीय है यदि यह संतुलित है।
+एक प्रबल व्यापकीकरण इस प्रकार है। एक हाइपरग्राफ {{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}}
+एक साधारण ग्राफ द्विभाज्य है यदि इसमें कोई विषम-लंबाई चक्र नहीं है। इसी तरह, एक हाइपरग्राफ को संतुलित किया जाता है यदि इसमें कोई विषम-लंबाई वाली ''परिधि''  न हो।हाइपरग्राफ में लंबाई {{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}}
+निम्नलिखित तुल्य हैं:<ref name="lp" />{{Rp|470–471}}
-* का हर आंशिक हाइपरग्राफ {{mvar|H}} (अर्थात, एक हाइपरग्राफ से व्युत्पन्न {{mvar|H}} कुछ हाइपरएजेज को हटाकर) में कोनिग संपत्ति है।
+* ''H'' के प्रत्येक भिन्नात्मक हाइपरग्राफ (अर्थात, कुछ हाइपरेजेज को हटाकर ''H'' से प्राप्त हाइपरग्राफ) में कोनिग गुण होता है।
-* का हर आंशिक हाइपरग्राफ {{mvar|H}} में यह गुण है कि इसकी अधिकतम डिग्री इसके न्यूनतम किनारे की रंग संख्या के बराबर है।
+* ''H'' के प्रत्येक भिन्नात्मक हाइपरग्राफ में यह गुण होता है  कि इसकी अधिकतम घात इसकी न्यूनतम [[बढ़त रंग]] संख्या के बराबर होती है।
-* {{mvar|H}} में हेली गुण है, और का प्रतिच्छेदन ग्राफ है {{mvar|H}} (सरल ग्राफ जिसमें शीर्ष हैं {{mvar|E}} और के दो तत्व {{mvar|E}} जुड़े हुए हैं यदि और केवल यदि वे प्रतिच्छेद करते हैं) एक आदर्श ग्राफ है।
+* {{mvar|H}} में [[हेली गुण]] है, और ''H'' का प्रतिच्छेदन ग्राफ (साधारण ग्राफ जिसमें शीर्ष {{mvar|E}} और {{mvar|E}} के दो तत्व जुड़े हुए हैं और केवल यदि वे प्रतिच्छेद करते हैं) एक [[पूर्ण ग्राफ]] है।
-== मिलान और पैकिंग ==
+== सुमेलन और संकुलन ==
-[[ पैकिंग सेट करें | पैकिंग समुच्चयकरें]] की समस्या हाइपरग्राफ मैचिंग के बराबर है।
+[[ पैकिंग सेट करें | समुच्चय]] [[संकुलन]] की समस्या हाइपरग्राफ सुमेलन के तुल्य है।
-एक [[वर्टेक्स पैकिंग]] | वर्टेक्स-पैकिंग एक (सरल) ग्राफ में एक सबसमुच्चयहै {{mvar|P}} इसके शीर्ष, जैसे कि कोई भी दो शीर्ष अंदर नहीं है {{mvar|P}} सटे हुए हैं।
+एक (सरल) ग्राफ में एक शीर्षिका-संकुलन इसके शीर्षों का एक उपसमुच्चय ''P'' है, जैसे कि ''P'' में कोई भी दो शीर्ष आसन्न नहीं हैं।
-ग्राफ़ में अधिकतम वर्टेक्स-पैकिंग खोजने की समस्या हाइपरग्राफ़ में अधिकतम मिलान खोजने की समस्या के बराबर है:<ref name="lp" />{{rp|467}}
+ग्राफ़ में अधिकतम शीर्षिका-संकुलन खोजने की समस्या हाइपरग्राफ़ में अधिकतम सुमेलन खोजने की समस्या के तुल्य है:<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=''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'}} जो आस-पास हैं {{mvar|v'}}). फिर हर वर्टेक्स-पैकिंग इन {{mvar|G}} में मेल खाता है {{math|St(''G'')}} और इसके विपरीत।
+* एक ग्राफ {{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'}} में हाइपर एज है {{math|Cl(''G'')}} में सभी गुट शामिल हैं {{mvar|G}} जिसमें शामिल है {{mvar|v'}}. फिर से, हर वर्टेक्स-पैकिंग इन {{mvar|G}} में मेल खाता है {{math|Cl(''G'')}} और इसके विपरीत। ध्यान दें कि {{math|Cl(''G'')}} से नहीं बनाया जा सकता {{mvar|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-समान हाइपरग्राफ से मिलान करने वाले हाइपरग्राफ का एक विशेष मामला।
+* [[3-विमीय सुमेलन]] - 3-एकसमान हाइपरग्राफ से सुमेलन करने वाले हाइपरग्राफ की एक विशेष स्थिति।
-* [[हाइपरग्राफ में वर्टेक्स कवर]]
+* [[हाइपरग्राफ में वर्टेक्स कवर|हाइपरग्राफ में '''<small>शीर्ष-आवरण</small>''']]
-* [[द्विदलीय हाइपरग्राफ]]
+* [[द्विदलीय हाइपरग्राफ|द्विभाज्य हाइपरग्राफ]]
-* रेनबो मैचिंग#हाइपरग्राफ
+* [[हाइपरग्राफ में मेघधनुष (रैन्बो) सुमेलन|हाइपरग्राफ में मेघधनुष सुमेलन]]
-* [[ डी-अंतराल हाइपरग्राफ ]] - एक अनंत हाइपरग्राफ जिसमें मैचिंग और कवरिंग नंबर के बीच कुछ संबंध होता है।
+* [[ डी-अंतराल हाइपरग्राफ ]]- एक अनंत हाइपरग्राफ जिसमें सुमेलन और आवरक संख्या के बीच कुछ संबंध होता है।
-* हाइपरग्राफ में जोड़ीदार गैर-असंबद्ध किनारों पर एर्डोस-को-राडो प्रमेय
+* हाइपरग्राफ में युग्‍मानूसार गैर-असंबद्ध किनारों पर [[एर्डोस-को-राडो प्रमेय]]
 == संदर्भ ==
 <references />
-[[Category: हाइपरग्राफ]] [[Category: मिलान (ग्राफ सिद्धांत)]]
-[[Category: Machine Translated Page]]
+[[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:हाइपरग्राफ]]

Anonymous

Search

हाइपरग्राफ में मिलान: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 18:39, 16 May 2023

Contents

परिभाषा

प्रतिच्छेदी हाइपरग्राफ

एक विशेष स्थिति के रूप में एक ग्राफ में सुमेलन

भिन्नात्मक सुमेलन

पूर्ण सुमेलन

संतुलित समुच्चय-परिवार

अधिकतम सुमेलन की गणना

सुमेलन और आवरण

कोनिग के गुण

सुमेलन और संकुलन

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

हाइपरग्राफ में मिलान: Difference between revisions

Latest revision as of 18:39, 16 May 2023

परिभाषा

प्रतिच्छेदी हाइपरग्राफ

एक विशेष स्थिति के रूप में एक ग्राफ में सुमेलन

भिन्नात्मक सुमेलन

पूर्ण सुमेलन

संतुलित समुच्चय-परिवार

अधिकतम सुमेलन की गणना

सुमेलन और आवरण

कोनिग के गुण

सुमेलन और संकुलन

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories