Dijoin
गणित में, एक डाइजॉइन एक निर्देशित ग्राफ के किनारों का एक उपसमुच्चय है, जिसमें वह गुण होता है जो डाइजॉइन में हर किनारे को संकुचित करता है और एक मजबूत रूप से जुड़ा हुआ ग्राफ उत्पन्न करता है। समान रूप से, एक डाइजॉइन किनारों का एक उपसमुच्चय है, जिसमें प्रत्येक डिकट के लिए, डिकट को पार करने वाला कम से कम एक किनारा शामिल होता है। यहाँ, एक डिकट शीर्षों का दो उपसमुच्चय में विभाजन है, ताकि प्रत्येक किनारा जिसका दोनों उपसमुच्चय में एक अंतिम बिंदु हो, पहले उपसमुच्चय से दूसरे तक निर्देशित हो। वुडल का अनुमान, जो इस क्षेत्र में एक अनसुलझी समस्या है, बताता है कि किसी भी निर्देशित ग्राफ में एक डिकट में किनारों की न्यूनतम संख्या (भारित न्यूनतम बंद) ग्राफ में पाए जाने वाले असंबद्ध डाइजॉइन की अधिकतम संख्या (डाइजॉइन की एक पैकिंग) के बराबर होती है। जैक एडमंड्स और रिक जाइल्स द्वारा प्रस्तुत अनुमान के एक आंशिक भारित संस्करण का अलेक्जेंडर श्रिजवर द्वारा खंडन किया गया था। लुचेसी-यंगर प्रमेय बताता है कि किसी भी दिए गए निर्देशित ग्राफ में एक डाइजोइन का न्यूनतम आकार, ग्राफ में पाए जाने वाले असंबद्ध डिकट्स की अधिकतम संख्या के बराबर होता है। भारित ग्राफ में न्यूनतम भार द्विभाजन बहुपद समय में पाया जा सकता है, और यह उप-प्रतिरूपी प्रवाह समस्या का एक विशेष मामला है। समतलीय ग्राफ में, डिजोइन और फीडबैक आर्क सेट दोहरी अवधारणाएँ हैं। समतल में अंतर्निहित एक निर्देशित ग्राफ का दोहरा ग्राफ, दिए गए ग्राफ के प्रत्येक चेहरे के लिए एक शीर्ष के साथ एक ग्राफ है, और दो दोहरे शीर्षों के बीच एक दोहरी धार है जब संबंधित दो चेहरे एक किनारे से अलग होते हैं। प्रत्येक दोहरे किनारे मूल ग्राफ किनारों में से एक को पार करते हैं, जो 90° घड़ी की दिशा में मुड़ते हैं। एक फीडबैक आर्क सेट किनारों का एक उपसमुच्चय है जिसमें प्रत्येक निर्देशित चक्र से कम से कम एक किनारा शामिल होता है। दिए गए ग्राफ में एक डाइजॉइन के लिए, किनारों का संबंधित सेट दोहरे ग्राफ में एक निर्देशित कटौती बनाता है, और इसके विपरीत। इन दो समस्याओं के बीच यह संबंध प्रतिक्रिया चाप सेट समस्या को समतलीय ग्राफ के लिए कुशलता से हल करने की अनुमति देता है, भले ही यह अन्य प्रकार के ग्राफ के लिए एनपी-हार्ड हो। संदर्भ निर्देशित ग्राफ