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

ग्राफ सिद्धांत में, हाइपरग्राफ में सुमेलन हाइपरेज का एक समुच्चय है, जिसमें हर दो हाइपरेज असंयुक्त होते हैं। यह एक ग्राफ में सुमेलन की धारणा का विस्तार है।^[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)$ और इसके विपरीत। ध्यान दें कि $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]

Anonymous

Search

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

Namespaces

More

Page actions

Contents

परिभाषा

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

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

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

पूर्ण सुमेलन

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

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

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

कोनिग के गुण

सुमेलन और पैकिंग

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

परिभाषा

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

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

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

पूर्ण सुमेलन

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

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

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

कोनिग के गुण

सुमेलन और पैकिंग

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories