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