Lucchesi–Younger theorem
নির্দেশিত গ্রাফের গণিতে, লুচেসি-ইয়ংগার উপপাদ্য হল ডিকাট এবং ডাইজোইনের মধ্যে একটি সম্পর্ক। এটি 1978 সালে ক্লাউডিও এল লুচেসি এবং ড্যানিয়েল এইচ ইয়ংগার দ্বারা প্রকাশিত হয়েছিল। তাদের প্রমাণ একটি অনুমানের সমাধান করেছিল যা প্রায় এক দশক আগে ইয়ংগার এবং নীল রবার্টসনের অপ্রকাশিত কাজে উপস্থাপিত হয়েছিল, যা ডাইজোইন এবং ফিডব্যাক আর্ক সেটের মধ্যে প্ল্যানার গ্রাফের দ্বৈততা দ্বারা অনুপ্রাণিত হয়েছিল। একটি ডাইকাট হল দুটি উপসেটে শীর্ষগুলির এমন একটি বিভাজন যাতে বিভাজনটি অতিক্রমকারী সমস্ত প্রান্ত একই দিকে তা করে। একটি ডাইজোইন হল প্রান্তগুলির একটি উপসেট যা সংকুচিত হলে একটি দৃঢ়ভাবে সংযুক্ত গ্রাফ তৈরি করে; সমতুল্যভাবে, এটি প্রান্তগুলির একটি উপসেট যা প্রতিটি বাঁধ থেকে কমপক্ষে একটি প্রান্ত অন্তর্ভুক্ত করে। যদি ডিকুটগুলির একটি সংগ্রহ সমস্ত বিচ্ছিন্ন হয়, তবে যে কোনও ডিজয়েনের এই ডিকুটগুলির প্রতিটি থেকে কমপক্ষে একটি প্রান্ত থাকতে হবে এবং কমপক্ষে সংগ্রহের আকারের সমান আকার থাকতে হবে। অতএব, যে কোনও গ্রাফে বিচ্ছিন্ন ডিকুটের সর্বাধিক সংখ্যা অবশ্যই একটি ডিজয়েনের ন্যূনতম আকারের চেয়ে কম বা সমান হতে হবে। লুচেসি-ইয়ংগার উপপাদ্য বলে যে এই সম্পর্ক সবসময়ই একটি সমতা। একটি ডাইজোইনের সর্বনিম্ন আকার একটি প্রদত্ত গ্রাফে পাওয়া যায় এমন সর্বাধিক সংখ্যক বিচ্ছিন্ন ডিকুটের সমান। তথ্যসূত্র নির্দেশিত গ্রাফ