Bipartite dimension
গ্রাফ তত্ত্ব এবং কম্বিনেটোরিয়াল অপ্টিমাইজেশনের গাণিতিক ক্ষেত্রে, G = (V, E) গ্রাফের দ্বিদলীয় মাত্রা বা দ্বিদলীয় আবরণ সংখ্যা হল দ্বিদলীয় সংখ্যার সর্বনিম্ন সংখ্যা (যা সম্পূর্ণ দ্বিদলীয় উপ-গ্রাফ), যা E-এর সমস্ত প্রান্তকে আচ্ছাদন করতে প্রয়োজন। জি-এর দ্বিদলীয় মাত্রা প্রায়শই ডি (জি) প্রতীক দ্বারা চিহ্নিত করা হয়। উদাহরণ একটি দ্বি-চুম্বকীয় প্রান্তের আবরণের জন্য একটি উদাহরণ নিম্নলিখিত চিত্রগুলিতে দেওয়া হয়েছেঃ কিছু গ্রাফের জন্য দ্বিদলীয় মাত্রার সূত্র n-ভার্টেক্স সম্পূর্ণ গ্রাফের দ্বিদলীয় মাত্রা হল। একটি 2n-ভার্টেক্স মুকুট গ্রাফের দ্বিদলীয় মাত্রা সমান, যেখানে কেন্দ্রীয় দ্বিপদী সহগের বিপরীত ফাংশন। ল্যাটিস গ্রাফের দ্বিদলীয় মাত্রা হল, যদি জোড় হয় এবং কিছু পূর্ণসংখ্যার জন্য; এবং অন্যথায়। কিছু বিশেষ গ্রাফের জন্য দ্বিদলীয় মাত্রা নির্ধারণ করুন। উদাহরণস্বরূপ, পথ আছে এবং চক্র আছে। দ্বিদলীয় মাত্রা গণনা একটি প্রদত্ত গ্রাফ জি-এর জন্য দ্বিদলীয় মাত্রা নির্ধারণের গণনামূলক কাজ একটি অপ্টিমাইজেশান সমস্যা। দ্বিদলীয় মাত্রার জন্য সিদ্ধান্তের সমস্যাটিকে এইভাবে বর্ণনা করা যেতে পারেঃ ইনস্ট্যান্সঃ একটি গ্রাফ এবং একটি ধনাত্মক পূর্ণসংখ্যা। প্রশ্নঃ জি কি সর্বাধিক দ্বি-চক্রযুক্ত একটি দ্বি-চক্রাকার প্রান্তের আবরণ স্বীকার করে? এই সমস্যাটি গ্যারি এবং জনসনের এনপি-সম্পূর্ণতা সম্পর্কিত ধ্রুপদী বইয়ে জিটি 18 সমস্যা হিসাবে প্রদর্শিত হয় এবং এটি সীমাবদ্ধ সেটগুলির পরিবারের উপর অন্য সিদ্ধান্তের সমস্যার একটি সহজবোধ্য সংস্কার। গ্যারি অ্যান্ড জনসনের বইয়ে এস. পি. 7 সমস্যা হিসাবে সেট বেসিস সমস্যাটি দেখা যায়। এখানে, একটি সসীম সেটের উপসেটগুলির একটি পরিবারের জন্য, একটি সেট বেসিস হল এর উপসেটগুলির আরেকটি পরিবার, যাতে প্রতিটি সেটকে কিছু বেসিস উপাদানের মিলন হিসাবে বর্ণনা করা যেতে পারে। সেট বেসিস সমস্যাটি এখন নিম্নরূপ দেওয়া হয়েছেঃ ইনস্ট্যান্সঃ একটি সসীম সেট, এর উপসেটগুলির একটি পরিবার এবং একটি ধনাত্মক পূর্ণসংখ্যা কে। প্রশ্নঃ সর্বাধিক আকারের জন্য কি কোনও নির্দিষ্ট ভিত্তি রয়েছে? এর পূর্ববর্তী গঠনে, দ্বিদলীয় গ্রাফের ক্ষেত্রেও সমস্যাটি এনপি-সম্পূর্ণ বলে প্রমাণিত হয়েছিল। একটি নির্দিষ্ট ভিত্তিতে সমস্যা হিসাবে সূত্রটি এর আগে দ্বারা এনপি-সম্পূর্ণ হিসাবে প্রমাণিত হয়েছিল। সমস্যাটি এনপি-শক্ত থেকে যায়, এমনকি যদি আমরা দ্বিদলীয় গ্রাফের দিকে আমাদের মনোযোগ সীমাবদ্ধ রাখি, যার দ্বিদলীয় মাত্রা সর্বাধিক হওয়ার নিশ্চয়তা দেওয়া হয়, যেখানে প্রদত্ত সমস্যার উদাহরণের আকারকে এন নির্দেশ করে। ইতিবাচক দিক থেকে, দ্বিদলীয় ডোমিনো-মুক্ত গ্রাফগুলিতে বহুপদী সময়ে সমস্যাটি সমাধানযোগ্য। আনুমানিক অ্যালগরিদমের অস্তিত্ব সম্পর্কে, প্রমাণ করা হয়েছে যে সমস্যাটি ভালভাবে আনুমানিক করা যায় না (পি ≤ এনপি ধরে নিয়ে)। প্রকৃতপক্ষে, ইতিমধ্যেই দ্বিদলীয় গ্রাফের জন্য, দ্বিদলীয় মাত্রাটি প্রতিটি স্থিরের জন্য এনপি-হার্ড থেকে আনুমানিক। এর বিপরীতে, সমস্যাটি স্থির-পরামিতি নির্ণয়যোগ্য প্রমাণ করা কার্নেলাইজেশন অ্যালগরিদম ডিজাইনের একটি অনুশীলন, যা পাঠ্য বইয়ে যেমন প্রদর্শিত হয়। ফলস্বরূপ কার্নেলের আকারের উপর একটি কংক্রিট বাঁধাও সরবরাহ করে, যা ইতিমধ্যে দ্বারা উন্নত করা হয়েছে। প্রকৃতপক্ষে, n শীর্ষে প্রদত্ত দ্বিদলীয় গ্রাফের জন্য, তার দ্বিদলীয় মাত্রা সর্বাধিক k অ্যাপ্লিকেশন কিনা তা সময়মতো সিদ্ধান্ত নেওয়া যেতে পারে একটি গ্রাফের দ্বিদলীয় মাত্রা নির্ধারণের সমস্যা কম্পিউটিংয়ের বিভিন্ন প্রসঙ্গে উপস্থিত হয়। উদাহরণস্বরূপ, কম্পিউটার সিস্টেমে, একটি সিস্টেমের বিভিন্ন ব্যবহারকারীদের বিভিন্ন সংস্থান অ্যাক্সেস করার অনুমতি দেওয়া বা অনুমতি দেওয়া যেতে পারে না। একটি ভূমিকা-ভিত্তিক প্রবেশাধিকার নিয়ন্ত্রণ ব্যবস্থায়, একটি ভূমিকা সম্পদের একটি সেটের প্রবেশাধিকার প্রদান করে। একজন ব্যবহারকারী একাধিক ভূমিকার মালিক হতে পারে এবং তার কিছু ভূমিকার দ্বারা প্রদত্ত সমস্ত সম্পদ অ্যাক্সেস করার অনুমতি রয়েছে। এছাড়াও, একটি ভূমিকা একাধিক ব্যবহারকারীর মালিকানাধীন হতে পারে। খনির সমস্যা হল ন্যূনতম ভূমিকা খুঁজে বের করা, যাতে প্রতিটি ব্যবহারকারীর জন্য, তার ভূমিকাগুলি একসাথে সমস্ত নির্দিষ্ট সম্পদে প্রবেশাধিকার প্রদান করে। সিস্টেমে সম্পদের সেটের সাথে ব্যবহারকারীদের সেট স্বাভাবিকভাবেই একটি দ্বিদলীয় গ্রাফকে প্ররোচিত করে, যার প্রান্তগুলি অনুমতি দেয়। এই গ্রাফের প্রতিটি দ্বি-চলক একটি সম্ভাব্য ভূমিকা, এবং ভূমিকা খনির সমস্যার সর্বোত্তম সমাধান সঠিকভাবে ন্যূনতম দ্বি-চলক প্রান্তের আবরণ। কম্পিউটার সুরক্ষার ক্ষেত্রেও অনুরূপ পরিস্থিতি জানা যায়, বিশেষ করে নিরাপদ সম্প্রচারের ক্ষেত্রে। সেই সেটআপে, একটি অনিরাপদ চ্যানেলের মাধ্যমে রিসিভারদের একটি সেটের কাছে বেশ কয়েকটি বার্তা পাঠাতে হবে। প্রতিটি বার্তাকে কিছু ক্রিপ্টোগ্রাফিক কী ব্যবহার করে এনক্রিপ্ট করতে হবে যা শুধুমাত্র কাঙ্ক্ষিত রিসিভারদেরই জানা থাকে। প্রতিটি রিসিভারের একাধিক এনক্রিপশন কী থাকতে পারে এবং প্রতিটি কী একাধিক রিসিভারের মধ্যে বিতরণ করা হবে। সর্বোত্তম মূল প্রজন্মের সমস্যা হল নিরাপদ সংক্রমণ নিশ্চিত করার জন্য এনক্রিপশন কীগুলির একটি ন্যূনতম সেট খুঁজে বের করা। উপরের হিসাবে, সমস্যাটি একটি দ্বিদলীয় গ্রাফ ব্যবহার করে মডেল করা যেতে পারে যার ন্যূনতম দ্বি-ক্লিক প্রান্তের আবরণ সর্বোত্তম কী প্রজন্মের সমস্যার সমাধানের সাথে মিলে যায়। জীববিজ্ঞানে একটি ভিন্ন প্রয়োগ রয়েছে, যেখানে হিউম্যান লিউকোসাইট অ্যান্টিজেন (এইচ. এল. এ) সেরোলজির গাণিতিক মডেলে ন্যূনতম দ্বি-চক্রীয় প্রান্তের আবরণ ব্যবহার করা হয়। আরও দেখুন এনপি-সম্পূর্ণ সমস্যাগুলির তালিকা ইন্টারসেকশন নম্বর (গ্রাফ তত্ত্ব), একটি গ্রাফ রেফারেন্সের প্রান্তগুলি আচ্ছাদন করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক চক্র। । । । । । । । । । । । । । । বাহ্যিক লিঙ্ক ডেভিড এপস্টেইনের দ্বিদলীয় মাত্রা সম্পর্কে ব্লগ এন্ট্রি এনপি-সম্পূর্ণ সমস্যা গ্রাফ অপরিবর্তনীয় দ্বিদলীয় গ্রাফ কভারিং সমস্যা