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

Revision as of 11:12, 11 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 56: / Line 56: @@
 एक हाइपरग्राफ ''H'' पर विचार करें जिसमें प्रत्येक हाइपरेज में अधिकतम {{mvar|n}} शीर्ष होते हैं। यदि {{mvar|H}} पूर्ण भिन्नात्मक सुमेलन को प्रविष्ट करता है, तो उसकी भिन्नात्मक सुमेलन संख्या कम से कम  {{math|{{frac|{{abs|''V''}} |''n''}}}} होती है| यदि  {{mvar|H}} में प्रत्येक हाइपरेज में यथार्थत: {{mvar|n}} शीर्ष होते हैं, तो इसकी भिन्नात्मक सुमेलन संख्या ठीक {{math|{{frac|{{abs|''V''}} |''n''}}}} पर होती है| <ref name=":0">{{Cite journal|last1=Nyman|first1=Kathryn|last2=Su|first2=Francis Edward|last3=Zerbib|first3=Shira|date=2020-01-02|title=कई टुकड़ों के साथ उचित विभाजन|url=http://www.sciencedirect.com/science/article/pii/S0166218X1930561X|journal=Discrete Applied Mathematics|volume=283|pages=115–122|language=en|arxiv=1710.09477|doi=10.1016/j.dam.2019.12.018|s2cid=119602376|issn=0166-218X}}</ref> {{Rp|sec.2}} यह इस तथ्य का व्यापकीकरण है कि, किसी ग्राफ़ में, एक पूर्ण सुमेलन का आकार{{math|{{frac|{{abs|''V''}} |2}}}} है |
-शीर्षों का एक समुच्चय {{mvar|V}}  दिया गया है, ''V'' के उपसमुच्चय के एक संग्रह {{mvar|E}} संतुलित कहा जाता है अगर हाइपरग्राफ {{math|(''V'',''E'')}} एक पूर्ण भिन्नात्मक सुमेलन स्वीकार करता है।
+शीर्षों का एक समुच्चय {{mvar|V}}  दिया गया है, ''V'' के उपसमुच्चय का एक संग्रह {{mvar|E}} संतुलित कहा जाता है अगर हाइपरग्राफ {{math|(''V'',''E'')}} एक पूर्ण भिन्नात्मक सुमेलन स्वीकार करता है।
 उदाहरण के लिए, अगर {{math|1=''V'' = {1,2,3,a,b,c} }} और {{math|1=''E'' = { {1,a}, {2,a}, {1,b}, {2,b}, {3,c} },}} तब {{mvar|E}} पूर्ण भिन्नात्मक सुमेलन के साथ संतुलित है {{math|{ 1/2, 1/2, 1/2, 1/2, 1 }.}}
@@ Line 62: / Line 62: @@
 हाइपरग्राफ में एक पूर्ण सुमेलन के अस्तित्व के लिए विभिन्न पर्याप्त शर्तें हैं:
-* [[हाइपरग्राफ के लिए हॉल-टाइप प्रमेय]] - समीपवासी (नैबर) के समुच्चय के आधार पर हॉल के विवाह (मेरिज) प्रमेय के अनुरूप पर्याप्त शर्तें प्रस्तुत करता है।
+* [[हाइपरग्राफ के लिए हॉल-टाइप प्रमेय]] - समीप (नैबर) के समुच्चय के आधार पर हॉल के विवाह (मेरिज) प्रमेय के अनुरूप पर्याप्त शर्तें प्रस्तुत करता है।
 * [[हाई-डिग्री हाइपरग्राफ में सटीक मिलान|उच्च-घात हाइपरग्राफ में]] [[पूर्ण सुमेलन]] - शीर्षों की घात के आधार पर [[हैमिल्टोनियन चक्रों पर डिराक के प्रमेय]] के समान पर्याप्त शर्तें प्रस्तुत करता है।
 * [[पीटर कीवाश|कीवाश]] और माइक्रॉफ्ट ने हाइपरग्राफ सुमेलन के लिए एक ज्यामितीय सिद्धांत विकसित किया।<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 78: / Line 78: @@
 [[हाइपरग्राफ|''हाइपरग्राफ'']] {{math|1=''H'' = (''V'', ''E'')}} में एक [[शीर्ष-आवरण|''शीर्ष-आवरण'']] ''V'' का एक उपसमुच्चय ''T'' है, जैसे कि प्रत्येक हाइपरेज में ''T'' का कम से कम एक शीर्ष होता है {{mvar|T}} (इसे [[अनुप्रस्थ]] या [[हिटिंग सेट|आघाती]] [[समुच्चय]] भी कहा जाता है, और यह समुच्चय आवरण के तुल्य है)। यह एक ग्राफ में ''[[वर्टेक्स कवर|शीर्ष-आवरण]]''  की धारणा का व्यापकीकरण है।
-हाइपरग्राफ {{mvar|H}} की '''शीर्ष-आवरण संख्या''' का सबसे छोटा छोटा आकार है। तिर्यक रेखा के लिए इसे अक्सर {{math|''τ''(''H'')}},<ref name="lp" />{{rp|466}}  से दर्शाया जाता है।
+हाइपरग्राफ {{mvar|H}} की '''शीर्ष-आवरण संख्या''' का सबसे छोटा आकार है। तिर्यक रेखा के लिए इसे अक्सर {{math|''τ''(''H'')}},<ref name="lp" />{{rp|466}}  से दर्शाया जाता है।
 एक '''भिन्नात्मक''' <small>'''शीर्ष-आवरण'''</small> एक ऐसा फलन है जो ''V'' में प्रत्येक शीर्ष को भार नियत करता है, जैसे कि ''E'' में प्रत्येक  हाइपरेज {{mvar|e}} के लिए, ''e'' में शीर्षों के भिन्नों का योग कम से कम 1 है। शीर्ष-आवरण एक भिन्नात्मक शीर्ष-आवरण की एक विशेष स्थिति है जिसमें सभी भार या तो 0 या 1 हैं। भिन्नात्मक शीर्ष-आवरण का आकार सभी शीर्षों के भिन्नों का योग होता है।
@@ Line 103: / Line 103: @@
 == कोनिग के गुण ==
-एक हाइपरग्राफ में '''कोनिग के गुण''' होते है यदि इसकी अधिकतम सुमेलन संख्या इसकी न्यूनतम शीर्ष-आवरण संख्या के बराबर होती है, अर्थात् यदि {{math|1=''ν''(''H'') = ''τ''(''H'')}} |कोनिग की प्रमेय (ग्राफ सिद्धांत) | [[कोनिग-एगेर्वरी प्रमेय]] से पता चलता है कि प्रत्येक [[द्विभाज्य ग्राफ]] में कोनिग गुण होता है। इस प्रमेय को हाइपरग्राफ तक विस्तारित करने के लिए, हमें द्विभाज्यता की धारणा को हाइपरग्राफ तक विस्तारित करने की आवश्यकता होती है।<ref name="lp" />{{rp|468}}
+एक हाइपरग्राफ में '''कोनिग के गुण''' होते है यदि इसकी अधिकतम सुमेलन संख्या इसकी न्यूनतम शीर्ष-आवरण संख्या के तुल्य होती है, अर्थात् यदि {{math|1=''ν''(''H'') = ''τ''(''H'')}} |[[कोनिग-एगेर्वरी प्रमेय]] से पता चलता है कि प्रत्येक [[द्विभाज्य ग्राफ]] में कोनिग गुण होता है। इस प्रमेय को हाइपरग्राफ तक विस्तारित करने के लिए, हमें द्विभाज्यता की धारणा को हाइपरग्राफ तक विस्तारित करने की आवश्यकता होती है।<ref name="lp" />{{rp|468}}
-एक साधारण व्यापकीकरण इस प्रकार है। एक हाइपरग्राफ को '''2-'''रंगीन कहा जाता है अगर इसके शीर्ष 2-रंगीन के हो सकते हैं ताकि प्रत्येक हाइपरेज (आकार कम से कम 2) में प्रत्येक रंगीन का कम से कम एक शीर्ष हो। एक वैकल्पिक पद का [[संपत्ति बी|गुण]] ''B'' है। एक साधारण ग्राफ द्विभाज्य है अगर यह 2-रंगीन है। हालांकि, कोनिग के गुण के बिना 2-रंगीन हाइपरग्राफ होते हैं। उदाहरण के लिए, {{math|1=''V'' = {1,2,3,4} }} के साथ हाइपरग्राफ पर मानना है जिसमें सभी त्रिक {{math|1=''E'' = { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} <nowiki>}</nowiki>}} | यह 2-रंगीन है, उदाहरण के लिए, हम {{math|{1,2} }}नीला और {3,4} सफेद रंग कर सकते हैं। हालाँकि, इसकी सुमेलन संख्या 1 है और इसका वर्टेक्स-कवर नंबर 2 है।
+एक साधारण व्यापकीकरण इस प्रकार है। एक हाइपरग्राफ को '''2-'''रंगीन कहा जाता है अगर इसके शीर्ष 2-रंगीन के हो सकते हैं ताकि प्रत्येक हाइपरेज (आकार कम से कम 2) में प्रत्येक रंग का कम से कम एक शीर्ष हो। एक वैकल्पिक पद का [[संपत्ति बी|गुण]] ''B'' है। एक साधारण ग्राफ द्विभाज्य है अगर यह 2-रंगीन है। हालांकि, कोनिग के गुण के बिना 2-रंगीन हाइपरग्राफ होते हैं। उदाहरण के लिए, {{math|1=''V'' = {1,2,3,4} }} के साथ हाइपरग्राफ पर मानना है जिसमें सभी त्रिक {{math|1=''E'' = { {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} <nowiki>}</nowiki>}} | यह 2-रंगीन है, उदाहरण के लिए, हम {{math|{1,2} }}नीला और {3,4} सफेद रंग कर सकते हैं। हालाँकि, इसकी सुमेलन संख्या 1 और शीर्ष-आवरण संख्या 2 है।
 एक प्रबल व्यापकीकरण इस प्रकार है। एक हाइपरग्राफ {{math|1=''H'' = (''V'', ''E'')}} और ''V'' का एक उपसमुच्चय {{mvar|V'}} दिया है,''H'' से ''V''<nowiki/>' का प्रतिबंध हाइपरग्राफ है जिसका शीर्ष ''V'' है, और ''E'' में प्रत्येक हाइपरेज {{mvar|e}} के लिए जो {{mvar|V'}} को प्रतिच्छेद करता है,इसमें एक हाइपरेज {{mvar|e'}} होता है जो ''e'' और ''V'' का प्रतिच्छेदन होता है। हाइपरग्राफ को '''संतुलित''' कहा जाता है यदि इसके सभी प्रतिबंध 2-रंगीय हैं।<ref>{{Citation|last=Berge|first=CLAUDE|title=CHAPTER 2 – Balanced Hypergraphs and Some Applications to Graph Theory|date=1973-01-01|url=http://www.sciencedirect.com/science/article/pii/B9780720422627500077|work=A Survey of Combinatorial Theory|pages=15–23|editor-last=Srivastava|editor-first=JAGDISH N.|publisher=North-Holland|language=en|isbn=978-0-7204-2262-7|access-date=2020-06-19}}</ref> एक साधारण ग्राफ द्विभाज्य है यदि यह संतुलित होता है।
@@ Line 125: / Line 125: @@
 * एक हाइपरग्राफ {{math|1=''H'' = (''V'', ''E'')}} दिया है, इसके प्रतिच्छेदन ग्राफ {{math|Int(''H'')}} को सरल ग्राफ के रूप में परिभाषित करें जिसके शीर्ष {{mvar|E}} और जिनके किनारे जोड़े {{math|(''e''{{sub|1}},''e''{{sub|2}})}} हैं  जैसे कि {{math|''e''{{sub|1}}}}, {{math|''e''{{sub|2}}}} में एक शीर्ष उभयनिष्ठ है। फिर {{mvar|H}} में प्रत्येक शीर्षिका-संकुलन {{math|Int(''H'')}} में सुमेलन और विपर्येण होता है।
-* एक ग्राफ {{math|1=''G'' = (''V' '', ''E' '')}} दिया गया है, इसके तारक हाइपरग्राफ {{math|St(''G'')}} को ''हाइपरग्राफ'' के रूप में परिभाषित करें जिसके शीर्ष {{mvar|E'}} हैं और जिनके हाइपरेज {{mvar|G}} के शीर्ष केतारक (स्टार) हैं (अर्थात, {{mvar|V'}} में प्रत्येक शीर्ष {{mvar|v'}} के लिए, {{math|St(''G'')}} में एक हाइपरेज होता है जिसमें  {{mvar|E'}} में वे सभी किनारे होते हैं जो ''v''' के आसन्न होते हैं)। फिर {{mvar|G}} में प्रत्येक शीर्षिका-संकुलन {{math|St(''G'')}} में सुमेलन और विपर्येण होता है।
+* एक ग्राफ {{math|1=''G'' = (''V' '', ''E' '')}} दिया गया है, इसके तारक हाइपरग्राफ {{math|St(''G'')}} को ''हाइपरग्राफ'' के रूप में परिभाषित करें जिसके शीर्ष {{mvar|E'}} हैं और जिनके हाइपरेज {{mvar|G}} के शीर्ष के तारक (स्टार) हैं (अर्थात, {{mvar|V'}} में प्रत्येक शीर्ष {{mvar|v'}} के लिए, {{math|St(''G'')}} में एक हाइपरेज होता है जिसमें  {{mvar|E'}} में वे सभी किनारे होते हैं जो ''v''' के आसन्न होते हैं)। फिर {{mvar|G}} में प्रत्येक शीर्षिका-संकुलन {{math|St(''G'')}} में सुमेलन और विपर्येण होता है।
-* वैकल्पिक रूप से, एक ग्राफ {{math|1=''G'' = (''V' '', ''E' '')}} दिया गया है, इसके क्लिक हाइपरग्राफ {{math|Cl(''G'')}} को हाइपरग्राफ के रूप में परिभाषित करें, जिसके शीर्षके {{mvar|G}} के [[क्लिक्स]] हैं, और {{mvar|V'}} में  प्रत्येक शीर्ष  {{mvar|v'}} के लिए, Cl(G) में एक हाइपरेज होता है जिसमें ''G'' में सभी क्लिक्स होते हैं, जिनमें ''v''<nowiki/>' होता है। फिर से, ''G'' में प्रत्येक शीर्षिका-संकुलन {{math|Cl(''G'')}} में सुमेलन और विपर्येण होता है। ध्यान दें कि [[बहुपद समय]] में {{mvar|G}} से ''Cl(G)'' का निर्माण नहीं किया जा सकता है, इसलिए इसे एनपी-दृढ़ता सिद्ध करने के लिए समानयन के रूप में उपयोग नहीं किया जा सकता है। लेकिन इसके कुछ सैद्धांतिक उपयोग हैं।
+* वैकल्पिक रूप से, एक ग्राफ {{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)'' का निर्माण नहीं किया जा सकता है, इसलिए इसे एनपी-दृढ़ता सिद्ध करने के लिए समानयन के रूप में उपयोग नहीं किया जा सकता है। लेकिन इसके कुछ सैद्धांतिक उपयोग हैं।
 == यह भी देखें ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 11:12, 11 May 2023

Contents

परिभाषा

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

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

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

पूर्ण सुमेलन

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

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

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

कोनिग के गुण

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 11:12, 11 May 2023

परिभाषा

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

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

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

पूर्ण सुमेलन

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

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

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

कोनिग के गुण

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories