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

ग्राफ सिद्धांत में, हाइपरग्राफ में सुमेलन हाइपरेज का एक समुच्चय है, जिसमें हर दो हाइपरेज असंयुक्त होते हैं। यह एक ग्राफ में सुमेलन की धारणा का विस्तार है।

परिभाषा

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

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

हाइपरग्राफ H की सुमेलन संख्या H में सुमेलन का सबसे बड़ा आकार है। इसे अक्सर ν(H) द्वारा निर्दिष्ट किया जाता है।

उदाहरण के लिए, 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|

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

आत्म पाश के बिना एक ग्राफ केवल 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).

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

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

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

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

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

• यदि प्रत्येक हाइपरएज इन H अधिक से अधिक शामिल हैं r कोने, फिर

  ${\frac {\nu ^{*}(H)}{\nu (H)}}\leq r-1+{\frac {1}{r}}.$

  विशेष रूप से, एक साधारण ग्राफ में:

  ${\frac {\nu ^{*}(H)}{\nu (H)}}\leq {\frac {3}{2}}.$

  • असमानता तेज है: चलो H_r हो r-समान परिमित प्रक्षेपी तल। तब ν(H_r) = 1 चूंकि हर दो हाइपरेज एक दूसरे को काटते हैं, और ν*(H_r) = r – 1 + 1/r भिन्नात्मक सुमेलन द्वारा जो भार प्रदान करता है 1/r प्रत्येक हाइपरेज के लिए (यह एक सुमेलन है क्योंकि प्रत्येक वर्टेक्स में निहित है r हाइपरएजेज, और इसका आकार है r – 1 + 1/r क्योंकि वहां हैं r² – 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 द्वारा सिद्ध किया गया था।

  • असमानता तेज है: चलो H_r- ऑर्डर का छोटा प्रोजेक्टिव प्लेन हो r – 1. तब ν(H_r-) = 1 चूंकि हर दो हाइपरेज एक दूसरे को काटते हैं, और ν*(H_r-) = r – 1 भिन्नात्मक सुमेलन द्वारा जो भार प्रदान करता है 1/r प्रत्येक हाइपरेज के लिए (वहाँ हैं r² – r हाइपरएज)।

सटीक मिलान

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

एक भिन्नात्मक सुमेलन {{mvar|M}प्रत्येक शीर्ष के लिए } को उत्तम कहा जाता है v में V, में hyperedges के अंशों का योग M युक्त v ठीक 1 है।

हाइपरग्राफ पर विचार करें H जिसमें प्रत्येक हाइपरेज में अधिकतम शामिल है n शिखर। अगर H पूर्ण भिन्नात्मक सुमेलन को स्वीकार करता है, तो उसकी भिन्नात्मक सुमेलन संख्या कम से कम होती है |V| ⁄n. यदि प्रत्येक हाइपरएज इन H बिल्कुल शामिल है n शीर्ष, तो इसकी भिन्नात्मक सुमेलन संख्या बिल्कुल पर है |V| ⁄n. यह इस तथ्य का सामान्यीकरण है कि, किसी ग्राफ़ में, पूर्ण सुमेलन का आकार है |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 }.

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

• हाइपरग्राफ के लिए हॉल-टाइप प्रमेय - पड़ोसियों के समुच्चयके आधार पर हॉल के विवाह प्रमेय के समान पर्याप्त स्थिति प्रस्तुत करता है।
• हाई-डिग्री हाइपरग्राफ में सटीक सुमेलन - कोने की डिग्री के आधार पर, हैमिल्टनियन चक्रों पर डिराक के प्रमेय के समान पर्याप्त स्थिति प्रस्तुत करता है।
• पीटर कीवाश और माइक्रॉफ्ट ने हाइपरग्राफ सुमेलन के लिए एक ज्यामितीय सिद्धांत विकसित किया।

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

समुच्चयका परिवार | सेट-परिवार E ग्राउंड समुच्चयपर V को संतुलित कहा जाता है (के संबंध में V) अगर हाइपरग्राफ H = (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}.

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

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

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

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

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

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

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

चूँकि हर हाइपरग्राफ के लिए वर्टेक्स-कवर एक भिन्नात्मक वर्टेक्स-कवर का एक विशेष मामला है H: <ब्लॉककोट>फ्रैक्शनल-वर्टेक्स-कवर-नंबर (H) ≤ वर्टेक्स-कवर-संख्या (H). </ब्लॉककोट> रैखिक प्रोग्रामिंग द्वैत का तात्पर्य है कि, प्रत्येक हाइपरग्राफ के लिए H: <ब्लॉककोट>फ्रैक्शनल-मैचिंग-नंबर (H) = आंशिक-वर्टेक्स-कवर-नंबर (H). </ब्लॉककोट> इसलिए, हर हाइपरग्राफ के लिए H::$\nu (H)\leq \nu ^{*}(H)=\tau ^{*}(H)\leq \tau (H)$ यदि प्रत्येक हाइपरेज का आकार H ज्यादा से ज्यादा है r तो अधिकतम सुमेलन में सभी हाइपरेज का मिलन एक वर्टेक्स-कवर है (यदि कोई खुला हाइपरेज था, तो हम इसे सुमेलन में जोड़ सकते थे)। इसलिए:

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

यह असमानता तंग है: समानता रखती है, उदाहरण के लिए, कब V रोकना r⋅ν(H) + r – 1 शिखर और E के सभी उपसमुच्चय शामिल हैं r शिखर।

हालाँकि, सामान्य तौर पर τ*(H) < r⋅ν(H), तब से ν*(H) < r⋅ν(H); हाइपरग्राफ में सुमेलन देखें#ऊपर भिन्नात्मक मिलान।

रायसर का अनुमान कहता है कि, प्रत्येक में r-मैच r-समान हाइपरग्राफ:

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

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

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

एक हाइपरग्राफ में कोनिग संपत्ति होती है यदि इसकी अधिकतम सुमेलन संख्या इसकी न्यूनतम वर्टेक्स-कवर संख्या के बराबर होती है, अर्थात् यदि ν(H) = τ(H). कोनिग की प्रमेय (ग्राफ सिद्धांत) | कोनिग-एगेर्वरी प्रमेय से पता चलता है कि प्रत्येक द्विदलीय ग्राफ में कोनिग गुण होता है। इस प्रमेय को हाइपरग्राफ तक विस्तारित करने के लिए, हमें द्विदलीयता की धारणा को हाइपरग्राफ तक विस्तारित करने की आवश्यकता है।

एक प्राकृतिक सामान्यीकरण इस प्रकार है। एक हाइपरग्राफ को 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-रंगीय हैं। एक साधारण ग्राफ द्विदलीय है यदि यह संतुलित है।

एक साधारण ग्राफ द्विदलीय है यदि इसमें कोई विषम-लंबाई चक्र नहीं है। इसी तरह, एक हाइपरग्राफ को संतुलित किया जाता है यदि इसमें कोई विषम-लंबाई वाला सर्किट न हो। लंबाई का एक सर्किट k हाइपरग्राफ में एक वैकल्पिक क्रम है (v₁, e₁, v₂, e₂, …, v_k, e_k, v_k+1 = v₁), जहां v_i भिन्न शीर्ष हैं और e_i अलग-अलग हाइपरेज हैं, और प्रत्येक हाइपरेज में इसके बाईं ओर शीर्ष और दाईं ओर शीर्ष होता है। सर्किट को असंतुलित कहा जाता है यदि प्रत्येक हाइपरेज में सर्किट में कोई अन्य कोने नहीं होते हैं। क्लॉड बर्ज ने साबित किया कि एक हाइपरग्राफ संतुलित है अगर और केवल अगर इसमें असंतुलित विषम-लंबाई सर्किट नहीं है। प्रत्येक संतुलित हाइपरग्राफ में कोनिग का गुण होता है।

निम्नलिखित समतुल्य हैं:

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

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

पैकिंग समुच्चयकरें की समस्या हाइपरग्राफ मैचिंग के बराबर है।

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

ग्राफ़ में अधिकतम वर्टेक्स-पैकिंग खोजने की समस्या हाइपरग्राफ़ में अधिकतम सुमेलन खोजने की समस्या के बराबर है:

• एक हाइपरग्राफ दिया H = (V, E), इसके प्रतिच्छेदन ग्राफ को परिभाषित करें Int(H) सरल ग्राफ के रूप में जिसके शीर्ष हैं E और जिनके किनारे जोड़े हैं (e₁,e₂) ऐसा है कि e₁, e₂ में एक शीर्ष उभयनिष्ठ है। फिर हर सुमेलन में 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-समान हाइपरग्राफ से सुमेलन करने वाले हाइपरग्राफ का एक विशेष मामला।
• हाइपरग्राफ में वर्टेक्स कवर
• द्विदलीय हाइपरग्राफ
• रेनबो मैचिंग#हाइपरग्राफ
• डी-अंतराल हाइपरग्राफ - एक अनंत हाइपरग्राफ जिसमें मैचिंग और कवरिंग नंबर के बीच कुछ संबंध होता है।
• हाइपरग्राफ में जोड़ीदार गैर-असंबद्ध किनारों पर एर्डोस-को-राडो प्रमेय