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