Maximum cut
একটি গ্রাফের জন্য, সর্বাধিক কাটা হল এমন একটি কাটা যার আকার কমপক্ষে অন্য যে কোনও কাটার আকারের। অর্থাৎ, এটি গ্রাফের শীর্ষগুলিকে দুটি পরিপূরক সেটে বিভক্ত করে এবং যাতে এবং এর মধ্যে প্রান্তের সংখ্যা যতটা সম্ভব বড় হয়। এই ধরনের কাটা খুঁজে পাওয়া ম্যাক্স-কাট সমস্যা হিসাবে পরিচিত। সমস্যাটি সহজভাবে নিম্নরূপ বর্ণনা করা যেতে পারে। একটি ভার্টেক্স সেটের একটি উপসেট চায় যাতে এবং পরিপূরক উপসেটটির মধ্যে প্রান্তের সংখ্যা যতটা সম্ভব বড় হয়। সমতুল্যভাবে, যতটা সম্ভব প্রান্ত সহ গ্রাফের একটি দ্বিদলীয় উপ-গ্রাফ চাই। ওয়েটেড ম্যাক্স-কাট নামে সমস্যার আরও একটি সাধারণ সংস্করণ রয়েছে, যেখানে প্রতিটি প্রান্ত একটি বাস্তব সংখ্যা, তার ওজনের সাথে যুক্ত এবং উদ্দেশ্য হল প্রান্তের সংখ্যার পরিবর্তে এবং তার পরিপূরকের মধ্যে প্রান্তের মোট ওজন সর্বাধিক করা। ইতিবাচক এবং নেতিবাচক উভয় ওজনের অনুমতি দেওয়া ওজনযুক্ত সর্বোচ্চ-কাটা সমস্যাটি সমস্ত ওজনে চিহ্নটি উল্টিয়ে সামান্যভাবে ওজনযুক্ত ন্যূনতম কাটা সমস্যায় রূপান্তরিত করা যেতে পারে। নিম্ন সীমা এডওয়ার্ডস শীর্ষ এবং প্রান্ত সহ একটি গ্রাফের উপর ম্যাক্স-কাটের জন্য নিম্নলিখিত দুটি নিম্ন সীমা অর্জন করেছেন ((ক) স্বেচ্ছাচারী, তবে (খ) এটি সংযুক্ত): (ক) (খ) বাউন্ড (খ) প্রায়শই এডওয়ার্ডস-এর্ডোস আবদ্ধ বলা হয় যেমন এরডোস এটি অনুমান করেছিলেন। এডওয়ার্ডস সম্ভাব্য পদ্ধতি ব্যবহার করে এডওয়ার্ডস-এর্ডোসকে আবদ্ধ প্রমাণ করেছিলেন; ক্রাউস্টন এট আল। রৈখিক বীজগণিত এবং ছদ্ম-বুলিয়ান ফাংশনের বিশ্লেষণ ব্যবহার করে আবদ্ধ প্রমাণ করা হয়েছে। ক্রোস্টন এট আল-এর প্রমাণ। স্বাক্ষরিত গ্রাফগুলিতে ব্যালেন্সড সাবগ্রাফ প্রবলেম (বিএসপি)-এর সাথে আবদ্ধ এডওয়ার্ডস-এর্ডোসকে প্রসারিত করার অনুমতি দেয়, অর্থাৎ। গ্রাফ যেখানে প্রতিটি প্রান্ত + বা-বরাদ্দ করা হয়। উপসেট এবং-এ বিভাজনের জন্য, একটি প্রান্ত ভারসাম্যপূর্ণ হয় যদি উভয় এবং এবং একই উপসেটে থাকে, বা এবং এবং ভিন্ন উপসেট হয়। বি. এস. পি-র লক্ষ্য হল সর্বাধিক সংখ্যক ভারসাম্যপূর্ণ প্রান্ত সহ একটি বিভাজন খুঁজে বের করা। এডওয়ার্ডস-এর্ডোস প্রতিটি সংযুক্ত স্বাক্ষরিত গ্রাফের জন্য একটি নিম্ন সীমা দেয়। বিশেষ শ্রেণীর গ্রাফের জন্য বাউন্ড (ক) উন্নত করা হয়েছিলঃ ত্রিভুজ-মুক্ত গ্রাফ, প্রদত্ত সর্বোচ্চ মাত্রার গ্রাফ,-মুক্ত গ্রাফ ইত্যাদি, উদাহরণস্বরূপ দেখুন। পোলজাক এবং তুর্জিক ওজনযুক্ত ম্যাক্স-কাটের সাথে আবদ্ধ এডওয়ার্ডস-এরদোসকে প্রসারিত করেছিলেনঃ কোথায় এবং কোথায় ওজন এবং এর সর্বনিম্ন ওজন বিস্তৃত গাছ। সম্প্রতি, গুটিন এবং ইয়েও ওজনযুক্ত গ্রাফের বিশেষ শ্রেণীর জন্য নির্বিচারে ওজনযুক্ত গ্রাফ এবং সীমানার জন্য পোলজাক-তুর্জিক প্রসারিত ওজনযুক্ত ম্যাক্স-কাটের জন্য বেশ কয়েকটি নিম্ন সীমা অর্জন করেছেন। গাণিতিক জটিলতা তাত্ত্বিক কম্পিউটার বিজ্ঞানে সর্বাধিক কাট সম্পর্কিত নিম্নলিখিত সিদ্ধান্ত সমস্যাটি ব্যাপকভাবে অধ্যয়ন করা হয়েছেঃ একটি গ্রাফ জি এবং একটি পূর্ণসংখ্যা কে দেওয়া হলে, জি-তে কমপক্ষে কে আকারের কাট রয়েছে কিনা তা নির্ধারণ করুন। এই সমস্যাটি এনপি-সম্পূর্ণ হিসাবে পরিচিত। এটি সহজেই দেখা যায় যে সমস্যাটি এনপিতে রয়েছেঃ একটি যথেষ্ট বড় কাটা উপস্থাপন করে একটি হ্যাঁ উত্তর প্রমাণ করা সহজ। সমস্যার এনপি-পূর্ণতা দেখানো যেতে পারে, উদাহরণস্বরূপ, সর্বাধিক 2-সন্তুষ্টি (সর্বাধিক সন্তোষজনক সমস্যার একটি সীমাবদ্ধতা) থেকে হ্রাস দ্বারা। সিদ্ধান্ত সমস্যার ওজনযুক্ত সংস্করণটি কার্পের 21টি এনপি-সম্পূর্ণ সমস্যার মধ্যে একটি ছিল; কার্প পার্টিশন সমস্যা থেকে হ্রাসের মাধ্যমে এনপি-সম্পূর্ণতা দেখিয়েছিলেন। উপরের সিদ্ধান্ত সমস্যার ক্যানোনিকাল অপ্টিমাইজেশন বৈকল্পিক সাধারণত সর্বাধিক-কাট সমস্যা বা সর্বাধিক-কাট হিসাবে পরিচিত এবং এটি এইভাবে সংজ্ঞায়িত করা হয়ঃ একটি গ্রাফ জি দেওয়া, একটি সর্বাধিক কাট খুঁজে বের করুন। অপ্টিমাইজেশান বৈকল্পিকটি এনপি-হার্ড হিসাবে পরিচিত। বিপরীত সমস্যা, একটি ন্যূনতম কাট খুঁজে পাওয়া ফোর্ড-ফুলকারসন অ্যালগরিদমের মাধ্যমে দক্ষতার সাথে সমাধানযোগ্য বলে জানা যায়। অ্যালগরিদম পলিনোমিয়াল-টাইম অ্যালগরিদম যেহেতু ম্যাক্স-কাট সমস্যাটি এনপি-হার্ড, সাধারণ গ্রাফগুলিতে ম্যাক্স-কাটের জন্য কোনও পলিনোমিয়াল-টাইম অ্যালগরিদম জানা যায় না। প্ল্যানার গ্রাফ যাইহোক, প্ল্যানার গ্রাফগুলিতে, সর্বাধিক কাটা সমস্যাটি রুট পরিদর্শন সমস্যার দ্বৈত (একটি সংক্ষিপ্ততম সফর খুঁজে বের করার সমস্যা যা কমপক্ষে একবার একটি গ্রাফের প্রতিটি প্রান্তে যায়), এই অর্থে যে একটি গ্রাফ জি-এর সর্বাধিক কাটা-সেটের অন্তর্গত নয় এমন প্রান্তগুলি জি-এর দ্বৈত গ্রাফের সর্বোত্তম পরিদর্শন সফরে দ্বিগুণ করা প্রান্তগুলির দ্বৈত। সর্বোত্তম পরিদর্শন সফর একটি স্ব-ছেদকারী বক্ররেখা তৈরি করে যা সমতলকে দুটি উপসেটে বিভক্ত করে, পয়েন্টগুলির উপসেট যার জন্য বক্ররেখার ঘূর্ণন সংখ্যা জোড় এবং উপসেট যার জন্য ঘূর্ণন সংখ্যা বিজোড়; এই দুটি উপসেট একটি কাটা গঠন করে যার মধ্যে সমস্ত প্রান্ত রয়েছে যার দ্বৈত প্রদর্শিত হয়। রুট পরিদর্শন সমস্যাটি বহুপদী সময়ে সমাধান করা যেতে পারে এবং এই দ্বৈততা প্ল্যানার গ্রাফের জন্য বহুপদী সময়ে সর্বাধিক কাটা সমস্যারও সমাধান করতে দেয়। তবে সর্বাধিক-বিভাজন সমস্যাটি এনপি-হার্ড হিসাবে পরিচিত। আনুমানিক অ্যালগরিদম ম্যাক্স-কাট সমস্যাটি এপিএক্স-হার্ড, যার অর্থ কোনও বহুপদী-সময় আনুমানিক স্কিম (পিটিএএস) নেই, ইচ্ছাকৃতভাবে সর্বোত্তম সমাধানের কাছাকাছি, যদি না পি = এনপি হয়। সুতরাং, প্রতিটি পরিচিত বহুপদী-সময় আনুমানিক অ্যালগরিদম একটি আনুমানিক অনুপাত কঠোরভাবে একের চেয়ে কম অর্জন করে। একটি সহজ র্যান্ডমাইজড 0.5-approximation অ্যালগরিদম রয়েছেঃ প্রতিটি শীর্ষের জন্য একটি মুদ্রা উল্টিয়ে নির্ধারণ করুন যে পার্টিশনের কোন অর্ধেকটি এটি বরাদ্দ করবে। প্রত্যাশিতভাবে, অর্ধেক প্রান্ত কাটা প্রান্ত হয়। এই অ্যালগরিদমটি শর্তাধীন সম্ভাবনার পদ্ধতির সাথে বিচ্ছিন্ন করা যেতে পারে; তাই একটি সহজ নির্ধারক বহুপদী-সময় 0.5-approximation অ্যালগরিদমও রয়েছে। এই ধরনের একটি অ্যালগরিদম প্রদত্ত গ্রাফের শীর্ষগুলির একটি নির্বিচারে বিভাজন দিয়ে শুরু হয় এবং বার বার বিভাজনের এক পাশ থেকে অন্য দিকে একটি শীর্ষকে সরিয়ে দেয়, প্রতিটি ধাপে সমাধানের উন্নতি করে, যতক্ষণ না এই ধরনের আর কোনও উন্নতি করা যায় না। পুনরাবৃত্তির সংখ্যা সর্বাধিক কারণ অ্যালগরিদম প্রতিটি ধাপে কমপক্ষে একটি প্রান্ত দ্বারা কাটকে উন্নত করে। যখন অ্যালগরিদমটি শেষ হয়, তখন প্রতিটি শীর্ষে আপতিত প্রান্তের কমপক্ষে অর্ধেক কাটার অন্তর্গত, কারণ অন্যথায় শীর্ষটি সরানো কাটার উন্নতি করবে। অতএব, কাটা অন্তত প্রান্ত অন্তর্ভুক্ত। সর্বাধিক পরিচিত আনুমানিক অনুপাত সহ ম্যাক্স-কাটের জন্য বহুপদী-সময়ের আনুমানিক অ্যালগরিদমটি গোম্যানস এবং উইলিয়ামসনের সেমিডিফাইনাইট প্রোগ্রামিং এবং র্যান্ডমাইজড রাউন্ডিং ব্যবহার করে একটি পদ্ধতি যা একটি আনুমানিক অনুপাত অর্জন করে যেখানে যদি অনন্য গেম অনুমানটি সত্য হয়, তবে এটি সর্বাধিক কাটের জন্য সর্বোত্তম সম্ভাব্য আনুমানিক অনুপাত। এই ধরনের অপ্রমাণিত অনুমান ব্যতীত, আনুমানিক অনুপাতের সাথে সর্বাধিক-কাটা মানটি আনুমানিকভাবে এনপি-হার্ড হিসাবে প্রমাণিত হয়েছে। মুক্ত-উৎস বাস্তবায়ন সহ এই সমস্যার জন্য 10টি অনুসন্ধানের একটি বর্ধিত বিশ্লেষণ রয়েছে। প্যারামিটারাইজড অ্যালগরিদম এবং কার্নেলাইজেশন যদিও প্রমাণ করা তুচ্ছ যে কমপক্ষে (প্যারামিটার) কে-এর একটি কাটা খুঁজে বের করার সমস্যাটি ফিক্সড-প্যারামিটার ট্র্যাক্টেবল (এফপিটি), তবে একটি গ্রাফ জি-এর কমপক্ষে এডওয়ার্ডস-এর্ডোস লোয়ার বাউন্ড (উপরের নিম্ন সীমা দেখুন) প্লাস (প্যারামিটার) কে-এর আকার কাটা আছে কিনা তা নির্ধারণ করার সমস্যার জন্য ফিক্সড-প্যারামিটার ট্র্যাক্টেবিলিটি দেখানো অনেক কঠিন। প্রমাণ করে যে সমস্যাটি সময়মতো সমাধান করা যেতে পারে এবং আকারের একটি কার্নেল স্বীকার করে। ক্রাউস্টন এবং অন্যান্য। নির্দিষ্ট-পরামিতি ট্র্যাক্টেবিলিটি ফলাফলটি ব্যালেন্সড সাবগ্রাফ প্রবলেমে (বিএসপি, উপরে নিম্ন সীমা দেখুন) প্রসারিত করে এবং কার্নেলের আকারকে (বিএসপি-র জন্যও ধারণ করে) উন্নত করে। ইটশেইড এবং মিনিক বি. এস. পি-র জন্য স্থির-পরামিতি ট্র্যাক্টেবিলিটি ফলাফল এবং কার্নেল-আকারের ফলাফলকে শীর্ষে উন্নত করেছে। অ্যাপ্লিকেশন মেশিন লার্নিং এর নোডগুলিকে বৈশিষ্ট্য হিসাবে এবং এর প্রান্তগুলিকে দূরত্ব হিসাবে বিবেচনা করে, ম্যাক্স কাট অ্যালগরিদম একটি গ্রাফকে দুটি পৃথক উপসেটে বিভক্ত করে। অন্য কথায়, বাইনারি শ্রেণিবিন্যাস সম্পাদনের জন্য এটি স্বাভাবিকভাবেই প্রয়োগ করা যেতে পারে। আরও সাধারণ শ্রেণিবিন্যাস অ্যালগরিদমের তুলনায়, এটির জন্য একটি বৈশিষ্ট্য স্থানের প্রয়োজন হয় না, শুধুমাত্র ভিতরের উপাদানগুলির মধ্যে দূরত্ব। তাত্ত্বিক পদার্থবিজ্ঞান পরিসংখ্যানগত পদার্থবিজ্ঞান এবং বিশৃঙ্খল সিস্টেমে, ম্যাক্স কাট সমস্যাটি একটি স্পিন গ্লাস মডেলের হ্যামিল্টনিয়ানকে ন্যূনতম করার সমতুল্য, সবচেয়ে সহজভাবে আইসিং মডেল। একটি গ্রাফ জি-তে আইসিং মডেলের জন্য এবং শুধুমাত্র নিকটতম-প্রতিবেশী মিথস্ক্রিয়া, হ্যামিল্টনিয়ান এখানে গ্রাফের প্রতিটি শীর্ষ হল একটি স্পিন সাইট যা একটি স্পিন মান নিতে পারে একটি স্পিন কনফিগারেশন পার্টিশন দুটি সেটে, স্পিন আপ সহ এবং স্পিন ডাউন সহ আমরা দুটি সেটকে সংযুক্ত করে এমন প্রান্তের সেট দিয়ে নির্দেশ করি। তারপরে আমরা হ্যামিল্টনিয়ানকে পুনরায় লিখতে পারি কারণ এই শক্তিকে হ্রাস করা মিনি-কাট সমস্যার সমতুল্য বা গ্রাফের ওজনকে ম্যাক্স-কাট সমস্যা হিসাবে সেট করে। সার্কিট ডিজাইন ভি. এল. এস. আই নকশায় ম্যাক্স কাট সমস্যার প্রয়োগ রয়েছে। আরও দেখুন মিনিমাম কাট মিনিমাম কে-কাট অড সাইকেল ট্রান্সভার্সাল, যা সবচেয়ে বড় দ্বিদলীয় প্ররোচিত সাবগ্রাফ আনফ্রেণ্ডলি পার্টিশনের জন্য জিজ্ঞাসা করার সমতুল্য, যা অসীম গ্রাফ নোট রেফারেন্সের জন্য একটি সম্পর্কিত ধারণা। । সর্বাধিক কাটা (অপ্টিমাইজেশন সংস্করণ) হল পরিশিষ্ট বি-তে এন. ডি. 14-এর সমস্যা (পৃষ্ঠা 399)। । । । । । । । । । সর্বাধিক কাটা (সিদ্ধান্ত সংস্করণ) হল পরিশিষ্ট এ2.2-এর এন. ডি. 16 সমস্যা। সর্বাধিক দ্বিদলীয় সাবগ্রাফ (সিদ্ধান্ত সংস্করণ) হল পরিশিষ্ট এ1.2-এ জিটি25 সমস্যা। । । । । । । । । । । । । । । । । । বাহ্যিক লিঙ্কগুলি পিয়েরলুইজি ক্রেসেনজি, ভিগো ক্যান, ম্যাগনুস হ্যাল্ডারসন, মারেক কার্পিনস্কি, গেরহার্ড ওয়েইজিঙ্গার (2000), "ম্যাক্সিমাম কাট", "এনপি অপ্টিমাইজেশন সমস্যার একটি সংকলন"। আন্দ্রেয়া ক্যাসিনি, নিকোলা রেবাগ্লিয়াটি (2012), "ম্যাক্স কাট সমাধানের জন্য একটি পাইথন লাইব্রেরি" গ্রাফ তত্ত্বটি গ্রাফ তত্ত্বে সমন্বিত অপ্টিমাইজেশান এনপি-সম্পূর্ণ সমস্যাগুলিকে অবজেক্ট করে।