Woodall's conjecture
নির্দেশিত গ্রাফের গণিতে, উডলের অনুমান হল ডিকাট এবং ডাইজোইনের মধ্যে একটি অপ্রমাণিত সম্পর্ক। এটি 1976 সালে ডগলাস উডল দ্বারা উপস্থাপিত হয়েছিল। বিবৃতি একটি ডিকট হল দুটি উপসেটে শীর্ষগুলির এমন একটি বিভাজন যাতে বিভাজনটি অতিক্রমকারী সমস্ত প্রান্ত একই দিকে তা করে। একটি ডাইজোইন হল প্রান্তগুলির একটি উপসেট যা সংকুচিত হলে একটি দৃঢ়ভাবে সংযুক্ত গ্রাফ তৈরি করে; সমতুল্যভাবে, এটি প্রান্তগুলির একটি উপসেট যা প্রতিটি বাঁধ থেকে কমপক্ষে একটি প্রান্ত অন্তর্ভুক্ত করে। যদি একটি ডিকাটে প্রান্তের সর্বনিম্ন সংখ্যা হয়, তবে গ্রাফে সর্বাধিক বিচ্ছিন্ন ডাইজোইন থাকতে পারে, কারণ প্রত্যেকটিতে অবশ্যই ক্ষুদ্রতম ডিকাট থেকে আলাদা প্রান্ত অন্তর্ভুক্ত করতে হবে। উডালের অনুমান বলে যে, এই ক্ষেত্রে, বিচ্ছিন্ন ডাইজোইন খুঁজে পাওয়া সর্বদা সম্ভব। অর্থাৎ, যে কোনও নির্দেশিত গ্রাফ-একটি ডাইকেটে প্রান্তের সর্বনিম্ন সংখ্যা-সর্বাধিক সংখ্যক বিচ্ছিন্ন ডাইজোইনের সমান যা গ্রাফে পাওয়া যায় (ডাইজোইনের একটি প্যাকিং)। আংশিক ফলাফল এটি একটি লোককাহিনীর ফলাফল যে এই উপপাদ্যটি নির্দেশিত গ্রাফের ক্ষেত্রে সত্য, যার সর্বনিম্ন ডাইকটের দুটি প্রান্ত রয়েছে। সমস্যার যে কোনও উদাহরণের ঘনীভবন গ্রহণ করে একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফে হ্রাস করা যেতে পারে, প্রতিটি দৃঢ়ভাবে সংযুক্ত উপাদানকে একক শীর্ষে সংকুচিত করে গঠিত একটি গ্রাফ। গ্রাফের আরেকটি শ্রেণী যার জন্য উপপাদ্যটি সত্য প্রমাণিত হয়েছে তা হল নির্দেশিত অ্যাসাইক্লিক গ্রাফ যেখানে প্রতিটি উৎস শীর্ষে (আগত প্রান্ত ছাড়া একটি শীর্ষে) প্রতিটি সিঙ্ক শীর্ষে (বহির্গামী প্রান্ত ছাড়া একটি শীর্ষে) যাওয়ার পথ থাকে। সম্পর্কিত ফলাফল জ্যাক এডমন্ডস এবং রিক জাইলস দ্বারা উপস্থাপিত অনুমানের একটি ভগ্নাংশ ওজনযুক্ত সংস্করণ আলেকজান্ডার শ্রিজভার দ্বারা অস্বীকার করা হয়েছিল। অন্য দিকে, লুচেসি-ইয়ংগার উপপাদ্য বলে যে একটি ডাইজোইনের সর্বনিম্ন আকার একটি প্রদত্ত আলেখ্যে পাওয়া যায় এমন সর্বাধিক সংখ্যক বিচ্ছিন্ন ডিকুটের সমান। তথ্যসূত্র বাহ্যিক লিঙ্ক নির্দেশিত গ্রাফ