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

Revision as of 21:24, 9 May 2023

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

परिभाषा

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

एक 'मिलान' में $H$ एक उपसमुच्चय है $M$ का $E$ , ऐसा है कि हर दो hyperedges $e 1$ और $e 2$ में $M$ में एक खाली चौराहा है (कोई शीर्ष समान नहीं है)।

हाइपरग्राफ की मिलान संख्या $H$ मिलान का सबसे बड़ा आकार है $H$ . इसे अक्सर द्वारा निरूपित किया जाता है $ν(H)$ .^[1]^: 466 ^[3] एक उदाहरण के रूप में, चलो $V$ समुच्चयहो ${1,2,3,4,5,6,7}.$ एक 3-समान हाइपरग्राफ पर विचार करें $V$ (एक हाइपरग्राफ जिसमें प्रत्येक हाइपरेज में ठीक 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$ , युक्त hyperedges के अंशों का योग $v$ अधिक से अधिक 1 है। एक मिलान भिन्नात्मक मिलान का एक विशेष मामला है जिसमें सभी अंश या तो 0 या 1 हैं। एक भिन्नात्मक मिलान का आकार सभी हाइपरेज के अंशों का योग है।

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

चूंकि मिलान प्रत्येक हाइपरग्राफ के लिए आंशिक मिलान का एक विशेष मामला है $H$ :

मिलान-संख्या( $H$ ) ≤ आंशिक-मिलान-संख्या ( $H$ )

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

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

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

यदि प्रत्येक हाइपरएज इन H अधिक से अधिक शामिल हैं r कोने, फिर
${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1+{\frac {1}{r}}.$
विशेष रूप से, एक साधारण ग्राफ में:^[5]
${\frac {\nu ^{*}(H)}{\nu (H)}}\leq {\frac {3}{2}}.$
- असमानता तेज है: चलो $H r$ हो $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$ क्योंकि वहां हैं $r 2 - 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)$ . यह András Gyárfás द्वारा सिद्ध किया गया था।^[4]
- असमानता तेज है: चलो $H r-$ ऑर्डर का छोटा प्रोजेक्टिव प्लेन हो $r - 1$ . तब $ν (H r -) = 1$ चूंकि हर दो हाइपरेज एक दूसरे को काटते हैं, और $ν *(H r -) = r - 1$ भिन्नात्मक मिलान द्वारा जो भार प्रदान करता है $1 / r$ प्रत्येक हाइपरेज के लिए (वहाँ हैं $r 2 - r$ हाइपरएज)।

सटीक मिलान

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

एक भिन्नात्मक मिलान {{mvar|M}प्रत्येक शीर्ष के लिए } को उत्तम कहा जाता है $v$ में $V$ , में hyperedges के अंशों का योग $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$ शिखरों का, एक संग्रह $E$ के उपसमुच्चय $V$ संतुलित कहा जाता है अगर हाइपरग्राफ $(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]

संतुलित सेट-फ़ैमिली

समुच्चयका परिवार | सेट-परिवार $E$ ग्राउंड समुच्चयपर $V$ को संतुलित कहा जाता है (के संबंध में $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)$ एक उपसमुच्चय है $T$ का $V$ , जैसे कि हर हाइपरेज इन $E$ में कम से कम एक शीर्ष शामिल है $T$ (इसे ट्रांसवर्सल (कॉम्बिनेटरिक्स) या हिटिंग समुच्चयभी कहा जाता है, और यह समुच्चयकवर समस्या के बराबर है)। यह एक ग्राफ में वर्टेक्स कवर की धारणा का सामान्यीकरण है।

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

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

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

चूँकि हर हाइपरग्राफ के लिए वर्टेक्स-कवर एक भिन्नात्मक वर्टेक्स-कवर का एक विशेष मामला है $H$ : <ब्लॉककोट>फ्रैक्शनल-वर्टेक्स-कवर-नंबर ( $H$ ) ≤ वर्टेक्स-कवर-संख्या ( $H$ ). </ब्लॉककोट> रैखिक प्रोग्रामिंग द्वैत का तात्पर्य है कि, प्रत्येक हाइपरग्राफ के लिए $H$ : <ब्लॉककोट>फ्रैक्शनल-मैचिंग-नंबर ( $H$ ) = आंशिक-वर्टेक्स-कवर-नंबर ( $H$ ). </ब्लॉककोट> इसलिए, हर हाइपरग्राफ के लिए $H$ :^[4]: $\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) में प्रत्येक रंग का कम से कम एक शीर्ष हो। एक वैकल्पिक शब्द संपत्ति बी है। एक साधारण ग्राफ द्विपक्षीय है अगर यह 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)$ और इसके विपरीत। ध्यान दें कि $Cl(G)$ से नहीं बनाया जा सकता $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 ]] में मिलान [[ hyperedges ]]ेज का एक सेट है, जिसमें हर दो हाइपरेजेज [[अलग करना सेट]] होते हैं। यह मिलान ([[ग्राफ सिद्धांत]]) की धारणा का विस्तार है।<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>
 == परिभाषा ==
-याद रखें कि एक हाइपरग्राफ {{mvar|H}} जोड़ी है {{math|(''V'', ''E'')}}, कहाँ {{mvar|V}} वर्टेक्स (ग्राफ सिद्धांत) का एक [[सेट (गणित)]] है और {{mvar|E}} के [[सबसेट]] का एक सेट है {{mvar|V}} हाइपरएज कहा जाता है। प्रत्येक हाइपरेज में एक या एक से अधिक कोने हो सकते हैं।
+याद रखें कि एक [[हाइपरग्राफ]] {{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}} में एक खाली चौराहा है (कोई शीर्ष समान नहीं है)।
 हाइपरग्राफ की मिलान संख्या {{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>
-एक उदाहरण के रूप में, चलो {{mvar|V}} सेट हो {{math|{1,2,3,4,5,6,7}.}} एक 3-समान हाइपरग्राफ पर विचार करें {{mvar|V}} (एक हाइपरग्राफ जिसमें प्रत्येक हाइपरेज में ठीक 3 कोने होते हैं)। होने देना {{mvar|H}} 4 हाइपरेज के साथ 3-समान हाइपरग्राफ बनें:
+एक उदाहरण के रूप में, चलो {{mvar|V}} समुच्चयहो {{math|{1,2,3,4,5,6,7}.}} एक 3-समान हाइपरग्राफ पर विचार करें {{mvar|V}} (एक हाइपरग्राफ जिसमें प्रत्येक हाइपरेज में ठीक 3 कोने होते हैं)। होने देना {{mvar|H}} 4 हाइपरेज के साथ 3-समान हाइपरग्राफ बनें:
 : {{math|{ {1,2,3}, {1,4,5}, {4,5,6}, {2,3,6} } }}
@@ Line 25: / Line 25: @@
 == एक विशेष मामले के रूप में एक ग्राफ में मिलान ==
-[[आत्म पाश]] के बिना एक ग्राफ केवल 2-समान हाइपरग्राफ है: प्रत्येक किनारे को दो कोने के सेट के रूप में माना जा सकता है जो इसे जोड़ता है। उदाहरण के लिए, यह 2-समान हाइपरग्राफ 4 कोने वाले ग्राफ़ का प्रतिनिधित्व करता है {{math|{1,2,3,4} }} और 3 किनारे:
+[[आत्म पाश]] के बिना एक ग्राफ केवल 2-समान हाइपरग्राफ है: प्रत्येक किनारे को दो कोने के समुच्चयके रूप में माना जा सकता है जो इसे जोड़ता है। उदाहरण के लिए, यह 2-समान हाइपरग्राफ 4 कोने वाले ग्राफ़ का प्रतिनिधित्व करता है {{math|{1,2,3,4} }} और 3 किनारे:
 : {{math|{ {1,3}, {1,4}, {2,4} } }}
-उपरोक्त परिभाषा के अनुसार, ग्राफ़ में मिलान एक सेट है {{mvar|M}} किनारों की, जैसे कि प्रत्येक दो किनारों में {{mvar|M}} एक खाली चौराहा है। यह कहने के बराबर है कि कोई भी दो किनारे अंदर नहीं हैं {{mvar|M}} एक ही शीर्ष के निकट हैं; यह बिल्कुल मिलान (ग्राफ सिद्धांत) की परिभाषा है।
+उपरोक्त परिभाषा के अनुसार, ग्राफ़ में मिलान एक समुच्चयहै {{mvar|M}} किनारों की, जैसे कि प्रत्येक दो किनारों में {{mvar|M}} एक खाली चौराहा है। यह कहने के बराबर है कि कोई भी दो किनारे अंदर नहीं हैं {{mvar|M}} एक ही शीर्ष के निकट हैं; यह बिल्कुल मिलान (ग्राफ सिद्धांत) की परिभाषा है।
 == [[आंशिक मिलान]] ==
@@ Line 53: / Line 53: @@
 हाइपरग्राफ पर विचार करें {{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}}}}.
-एक सेट दिया {{mvar|V}} शिखरों का, एक संग्रह {{mvar|E}} के उपसमुच्चय {{mvar|V}} संतुलित कहा जाता है अगर हाइपरग्राफ {{math|(''V'',''E'')}} पूर्ण आंशिक मिलान स्वीकार करता है।
+एक समुच्चयदिया {{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 }.}}
@@ Line 59: / Line 59: @@
 हाइपरग्राफ में एक पूर्ण मिलान के अस्तित्व के लिए विभिन्न पर्याप्त शर्तें हैं:
-* [[हाइपरग्राफ के लिए हॉल-टाइप प्रमेय]] - पड़ोसियों के सेट के आधार पर हॉल के विवाह प्रमेय के समान पर्याप्त स्थिति प्रस्तुत करता है।
+* [[हाइपरग्राफ के लिए हॉल-टाइप प्रमेय]] - पड़ोसियों के समुच्चयके आधार पर हॉल के विवाह प्रमेय के समान पर्याप्त स्थिति प्रस्तुत करता है।
 * [[हाई-डिग्री हाइपरग्राफ में सटीक मिलान]] - कोने की डिग्री के आधार पर, हैमिल्टनियन चक्रों पर डिराक के प्रमेय के समान पर्याप्त स्थिति प्रस्तुत करता है।
 * [[पीटर कीवाश]] और माइक्रॉफ्ट ने हाइपरग्राफ मिलान के लिए एक ज्यामितीय सिद्धांत विकसित किया।<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>
@@ Line 65: / Line 65: @@
 == संतुलित सेट-फ़ैमिली ==
-[[सेट का परिवार]] | सेट-परिवार {{mvar|E}} ग्राउंड सेट पर {{mvar|V}} को संतुलित कहा जाता है (के संबंध में {{mvar|V}}) अगर हाइपरग्राफ {{math|1=''H'' = (''V'', ''E'')}} पूर्ण आंशिक मिलान स्वीकार करता है।<ref name=":0" /> {{Rp|sec.2}}
+[[सेट का परिवार|समुच्चयका परिवार]] | सेट-परिवार {{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}.}}
+उदाहरण के लिए, वर्टेक्स समुच्चयपर विचार करें {{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}.}}
 == अधिकतम मिलान की गणना ==
@@ Line 73: / Line 73: @@
 == मिलाना और ढकना ==
-हाइपरग्राफ में वर्टेक्स कवर | हाइपरग्राफ में वर्टेक्स-कवर {{math|1=''H'' = (''V'', ''E'')}} एक उपसमुच्चय है {{mvar|T}} का {{mvar|V}}, जैसे कि हर हाइपरेज इन {{mvar|E}} में कम से कम एक शीर्ष शामिल है {{mvar|T}} (इसे ट्रांसवर्सल (कॉम्बिनेटरिक्स) या [[हिटिंग सेट]] भी कहा जाता है, और यह सेट कवर समस्या के बराबर है)। यह एक ग्राफ में [[वर्टेक्स कवर]] की धारणा का सामान्यीकरण है।
+हाइपरग्राफ में वर्टेक्स कवर | हाइपरग्राफ में वर्टेक्स-कवर {{math|1=''H'' = (''V'', ''E'')}} एक उपसमुच्चय है {{mvar|T}} का {{mvar|V}}, जैसे कि हर हाइपरेज इन {{mvar|E}} में कम से कम एक शीर्ष शामिल है {{mvar|T}} (इसे ट्रांसवर्सल (कॉम्बिनेटरिक्स) या [[हिटिंग सेट|हिटिंग]] समुच्चयभी कहा जाता है, और यह समुच्चयकवर समस्या के बराबर है)। यह एक ग्राफ में [[वर्टेक्स कवर]] की धारणा का सामान्यीकरण है।
 हाइपरग्राफ का वर्टेक्स-कवर नंबर {{mvar|H}} वर्टेक्स कवर का सबसे छोटा आकार है {{mvar|H}}. इसे अक्सर द्वारा निरूपित किया जाता है {{math|''τ''(''H'')}},<ref name="lp" />{{rp|466}} अनुप्रस्थ के लिए।
@@ Line 112: / Line 112: @@
 == मिलान और पैकिंग ==
-[[ पैकिंग सेट करें ]] की समस्या हाइपरग्राफ मैचिंग के बराबर है।
+[[ पैकिंग सेट करें | पैकिंग समुच्चयकरें]] की समस्या हाइपरग्राफ मैचिंग के बराबर है।
-एक [[वर्टेक्स पैकिंग]] | वर्टेक्स-पैकिंग एक (सरल) ग्राफ में एक सबसेट है {{mvar|P}} इसके शीर्ष, जैसे कि कोई भी दो शीर्ष अंदर नहीं है {{mvar|P}} सटे हुए हैं।
+एक [[वर्टेक्स पैकिंग]] | वर्टेक्स-पैकिंग एक (सरल) ग्राफ में एक सबसमुच्चयहै {{mvar|P}} इसके शीर्ष, जैसे कि कोई भी दो शीर्ष अंदर नहीं है {{mvar|P}} सटे हुए हैं।
 ग्राफ़ में अधिकतम वर्टेक्स-पैकिंग खोजने की समस्या हाइपरग्राफ़ में अधिकतम मिलान खोजने की समस्या के बराबर है:<ref name="lp" />{{rp|467}}

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 21:24, 9 May 2023

Contents

परिभाषा

इंटरसेक्टिंग हाइपरग्राफ

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

आंशिक मिलान

सटीक मिलान

संतुलित सेट-फ़ैमिली

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

मिलाना और ढकना

कोनिग की संपत्ति

मिलान और पैकिंग

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 21:24, 9 May 2023

परिभाषा

इंटरसेक्टिंग हाइपरग्राफ

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

आंशिक मिलान

सटीक मिलान

संतुलित सेट-फ़ैमिली

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

मिलाना और ढकना

कोनिग की संपत्ति

मिलान और पैकिंग

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories