Bipartite dimension
ग्राफ सिद्धांत और संयोजन अनुकूलन के गणितीय क्षेत्रों में, G = (V, E) ग्राफ का द्विदलीय आयाम या द्विदलीय आवरण संख्या द्विदलीय की न्यूनतम संख्या है (जो कि पूर्ण द्विदलीय उपलेख है), जो E में सभी किनारों को कवर करने के लिए आवश्यक है। जी के द्विदलीय आयाम को अक्सर प्रतीक डी (जी) द्वारा दर्शाया जाता है। उदाहरण द्विस्तरीय किनारे के आवरण का एक उदाहरण निम्नलिखित आरेखों में दिया गया हैः कुछ आरेखों के लिए द्विस्तरीय आयाम सूत्र एन-वर्टेक्स पूर्ण आरेख का द्विस्तरीय आयाम है। 2n-वर्टेक्स क्राउन ग्राफ का द्विदलीय आयाम बराबर होता है, जहाँ केंद्रीय द्विपद गुणांक का व्युत्क्रम फलन होता है। जाली ग्राफ का द्विदलीय आयाम है, यदि सम है और कुछ पूर्णांकों के लिए; और अन्यथा है। कुछ विशेष आलेखों के लिए द्विदलीय आयाम निर्धारित करें। उदाहरण के लिए, पथ है और चक्र है। द्विदलीय आयाम की गणना किसी दिए गए ग्राफ जी के लिए द्विदलीय आयाम निर्धारित करने का कम्प्यूटेशनल कार्य एक अनुकूलन समस्या है। द्विदलीय आयाम के लिए निर्णय समस्या को इस प्रकार व्यक्त किया जा सकता हैः तत्कालः एक ग्राफ और एक सकारात्मक पूर्णांक। प्रश्नः क्या जी एक द्वि-चक्रीय किनारे के आवरण को स्वीकार करता है जिसमें अधिकांश द्वि-चक्रीय होते हैं? यह समस्या गैरी और जॉनसन की एन. पी.-पूर्णता पर शास्त्रीय पुस्तक में समस्या जी. टी. 18 के रूप में दिखाई देती है, और सीमित समूहों के परिवारों पर एक अन्य निर्णय समस्या का एक सीधा सुधार है। गैरी एंड जॉनसन की पुस्तक में एस. पी. 7 समस्या के रूप में निर्धारित आधार समस्या दिखाई देती है। यहाँ, एक परिमित समूह के उपसमुच्चय के परिवार के लिए, एक सेट आधार के उपसमुच्चय का एक और परिवार है, जैसे कि प्रत्येक समूह को कुछ आधार तत्वों के संघ के रूप में वर्णित किया जा सकता है। सेट आधार समस्या अब इस प्रकार दी गई हैः तत्कालः एक परिमित समुच्चय, के उपसमुच्चय का एक परिवार, और एक सकारात्मक पूर्णांक k। प्रश्नः क्या आकार का एक निर्धारित आधार मौजूद है? अपने पूर्व सूत्रीकरण में, द्विदलीय ग्राफों के लिए भी समस्या एन. पी.-पूर्ण साबित हुई थी। एक निर्धारित आधार समस्या के रूप में सूत्रीकरण पहले एन. पी.-पूर्ण साबित हुआ था। समस्या एन. पी.-कठोर बनी रहती है, भले ही हम अपना ध्यान द्विदलीय आलेखों तक ही सीमित रखें, जिनके द्विदलीय आयाम के अधिक से अधिक होने की गारंटी है, जिसमें एन दिए गए समस्या के उदाहरण के आकार को दर्शाता है। सकारात्मक पक्ष पर, समस्या द्विदलीय डोमिनोज़-मुक्त ग्राफ पर बहुपद समय में हल करने योग्य है। सन्निकटन एल्गोरिदम के अस्तित्व के संबंध में, यह साबित हुआ कि समस्या को अच्छी तरह से अनुमानित नहीं किया जा सकता है (पी § एनपी मानते हुए)। वास्तव में, द्विदलीय आयाम पहले से ही द्विदलीय ग्राफ के लिए, प्रत्येक निश्चित के लिए एन. पी.-कठिन से अनुमानित है। इसके विपरीत, यह साबित करना कि समस्या निश्चित-पैरामीटर ट्रैक्टेबल है, कर्नेलाइजेशन एल्गोरिदम को डिजाइन करने में एक अभ्यास है, जो पाठ्यपुस्तक में इस प्रकार दिखाई देता है। परिणामी गुठली के आकार पर एक ठोस बंधन भी प्रदान करता है, जिसमें इस बीच सुधार किया गया है। वास्तव में, n शीर्षों पर दिए गए द्विदलीय ग्राफ के लिए, यह समय पर तय किया जा सकता है कि क्या इसका द्विदलीय आयाम अधिकतम k अनुप्रयोगों पर है। उदाहरण के लिए, कंप्यूटर प्रणालियों में, एक प्रणाली के विभिन्न उपयोगकर्ताओं को विभिन्न संसाधनों तक पहुँचने की अनुमति या अनुमति नहीं दी जा सकती है। भूमिका-आधारित अभिगम नियंत्रण प्रणाली में, एक भूमिका संसाधनों के एक समूह तक पहुंच अधिकार प्रदान करती है। एक उपयोगकर्ता कई भूमिकाओं का मालिक हो सकता है, और उसे अपनी कुछ भूमिकाओं द्वारा दिए गए सभी संसाधनों तक पहुंचने की अनुमति है। इसके अलावा, एक भूमिका कई उपयोगकर्ताओं के स्वामित्व में हो सकती है। भूमिका खनन समस्या भूमिकाओं का एक न्यूनतम समूह खोजना है, जैसे कि प्रत्येक उपयोगकर्ता के लिए, उसकी भूमिकाओं को एक साथ सभी निर्दिष्ट संसाधनों तक पहुंच प्रदान करें। प्रणाली में संसाधनों के समूह के साथ उपयोगकर्ताओं का समूह स्वाभाविक रूप से एक द्विदलीय ग्राफ को प्रेरित करता है, जिसके किनारे अनुमतियाँ हैं। इस ग्राफ में प्रत्येक द्वि-चक्रीय एक संभावित भूमिका है, और भूमिका खनन समस्या का इष्टतम समाधान सटीक रूप से न्यूनतम द्वि-चक्रीय किनारे कवर हैं। इसी तरह का परिदृश्य कंप्यूटर सुरक्षा में जाना जाता है, विशेष रूप से सुरक्षित प्रसारण में। उस व्यवस्था में, कई संदेशों को एक असुरक्षित चैनल पर प्राप्तकर्ताओं के एक समूह को भेजने की आवश्यकता होती है। प्रत्येक संदेश को कुछ क्रिप्टोग्राफिक कुंजी का उपयोग करके एन्क्रिप्ट किया जाना चाहिए जो केवल इच्छित प्राप्तकर्ताओं को ही पता हो। प्रत्येक रिसीवर के पास कई एन्क्रिप्शन कुंजी हो सकती हैं, और प्रत्येक कुंजी को कई रिसीवरों को वितरित किया जाएगा। सुरक्षित संचरण सुनिश्चित करने के लिए एन्क्रिप्शन कुंजियों का न्यूनतम सेट ढूंढना इष्टतम कुंजी पीढ़ी की समस्या है। ऊपर के रूप में, समस्या को एक द्विदलीय ग्राफ का उपयोग करके मॉडल किया जा सकता है जिसका न्यूनतम द्वि-चक्रीय किनारा कवर इष्टतम कुंजी पीढ़ी समस्या के समाधान के साथ मेल खाता है। एक अलग अनुप्रयोग जीव विज्ञान में निहित है, जहां मानव ल्यूकोसाइट एंटीजन (एच. एल. ए.) सीरोलॉजी के गणितीय मॉडल में न्यूनतम बाइक्लिक एज कवर का उपयोग किया जाता है। एन. पी.-पूर्ण समस्याओं की सूची भी देखें इंटरसेक्शन संख्या (ग्राफ सिद्धांत), एक ग्राफ संदर्भ के किनारों को कवर करने के लिए आवश्यक गुटों की न्यूनतम संख्या। .. .. .. .. .. .. .. .. .. .. .. .. .. .. बाहरी लिंक डेविड एपस्टीन एन. पी. द्वारा द्विदलीय आयाम के बारे में ब्लॉग प्रविष्टि-पूर्ण समस्याएं ग्राफ अपरिवर्तनीय द्विदलीय ग्राफ कवर करने वाली समस्याएं