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