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