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