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

Revision as of 17:23, 10 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$ . इसे अक्सर द्वारा निरूपित किया जाता है $τ (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 75: / Line 75: @@
 हाइपरग्राफ में अधिकतम-गणनांक सुमेलन जाँच परिणाम की समस्या, इस प्रकार गणना करना <math>\nu(H)</math>, 3-एकसमान हाइपरग्राफ के लिए भी एनपी-ठोस है ([[3-आयामी मिलान|3-विमीय]] सुमेलन देखें)। यह सरल (2-एकसमान) ग्राफ़ की स्थिति के विपरीत है जिसमें बहुपद समय में [[अधिकतम-गणनांक सुमेलन]] की गणना की जा सकती है।
-== मिलाना और ढकना ==
+== सुमेलन और आवरण ==
-हाइपरग्राफ में वर्टेक्स कवर | हाइपरग्राफ में वर्टेक्स-कवर {{math|1=''H'' = (''V'', ''E'')}} एक उपसमुच्चय है {{mvar|T}} का {{mvar|V}}, जैसे कि हर हाइपरेज इन {{mvar|E}} में कम से कम एक शीर्ष शामिल है {{mvar|T}} (इसे ट्रांसवर्सल (कॉम्बिनेटरिक्स) या [[हिटिंग सेट|हिटिंग]] समुच्चयभी कहा जाता है, और यह समुच्चयकवर समस्या के बराबर है)। यह एक ग्राफ में [[वर्टेक्स कवर]] की धारणा का सामान्यीकरण है।
+[[हाइपरग्राफ|''हाइपरग्राफ'']] {{math|1=''H'' = (''V'', ''E'')}} में एक [[शीर्ष-आवरण|''शीर्ष-आवरण'']] ''V'' का एक उपसमुच्चय ''T'' है, जैसे कि प्रत्येक हाइपरेज में ''T'' का कम से कम एक शीर्ष होता है {{mvar|T}} (इसे [[अनुप्रस्थ]] या [[हिटिंग सेट|आघाती]] [[समुच्चय]] भी कहा जाता है, और यह समुच्चय आवरण के तुल्य है)। यह एक ग्राफ में ''[[वर्टेक्स कवर|शीर्ष-आवरण]]''  की धारणा का व्यापकीकरण है।
 हाइपरग्राफ का वर्टेक्स-कवर नंबर {{mvar|H}} वर्टेक्स कवर का सबसे छोटा आकार है {{mvar|H}}. इसे अक्सर द्वारा निरूपित किया जाता है {{math|''τ''(''H'')}},<ref name="lp" />{{rp|466}} अनुप्रस्थ के लिए।

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 17:23, 10 May 2023

Contents

परिभाषा

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

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

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

पूर्ण सुमेलन

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 17:23, 10 May 2023

परिभाषा

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

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

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

पूर्ण सुमेलन

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

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

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories