সর্বাধিক দ্বিপার্শ্বিক ম্যাচিং-এর জন্য কুহনের অ্যালগরিদম#

সমস্যা#

আপনাকে একটি দ্বিপার্শ্বিক গ্রাফ $G$ দেওয়া হয় যা $n$ টি ভার্টেক্স এবং $m$ টি এজ রয়েছে। সর্বাধিক ম্যাচিং খুঁজে বের করুন, অর্থাৎ যতটা সম্ভব এজ নির্বাচন করুন যাতে কোনো নির্বাচিত এজ অন্য কোনো নির্বাচিত এজের সাথে একটি ভার্টেক্স শেয়ার না করে।

অ্যালগরিদম বর্ণনা#

প্রয়োজনীয় সংজ্ঞা#

• একটি ম্যাচিং $M$ হল একটি গ্রাফের জোড়ায় অ-সংলগ্ন এজের একটি সেট (অন্য কথায়, সেটের একাধিকেরও বেশি এজ গ্রাফ $M$ এর যেকোনো ভার্টেক্সের সাথে সংযুক্ত হওয়া উচিত নয়)। একটি ম্যাচিং-এর কার্ডিনালিটি এতে এজের সংখ্যা। সেই সমস্ত ভার্টেক্স যাদের ম্যাচিং থেকে একটি সংলগ্ন এজ রয়েছে (অর্থাৎ, যার $M$ দ্বারা গঠিত সাবগ্রাফে ঠিক একটি ডিগ্রি রয়েছে) এই ম্যাচিং দ্বারা স্যাচুরেট বলা হয়।

• একটি ম্যাক্সিমাল ম্যাচিং একটি গ্রাফ $G$ এর একটি ম্যাচিং $M$ যা অন্য কোনো ম্যাচিং-এর সাবসেট নয়।

• একটি সর্বাধিক ম্যাচিং (সর্বাধিক-কার্ডিনালিটি ম্যাচিং নামেও পরিচিত) একটি ম্যাচিং যা সর্বাধিক সম্ভাব্য সংখ্যক এজ রয়েছে। প্রতিটি সর্বাধিক ম্যাচিং একটি ম্যাক্সিমাল ম্যাচিং।

• দৈর্ঘ্য $k$ এর একটি পথ এখানে একটি সরল পথ (অর্থাৎ পুনরাবৃত্ত ভার্টেক্স বা এজ ধারণ করে না) $k$ টি এজ রয়েছে, অন্যথায় নির্দিষ্ট না হলে।

• একটি পরিবর্তনকারী পথ (একটি দ্বিপার্শ্বিক গ্রাফে, কিছু ম্যাচিং-এর সাথে) একটি পথ যেখানে এজগুলি ম্যাচিং-এ অ্যালটারনেটভাবে অন্তর্গত / অন্তর্গত নয়।

• একটি বর্ধনশীল পথ (একটি দ্বিপার্শ্বিক গ্রাফে, কিছু ম্যাচিং-এর সাথে) একটি পরিবর্তনকারী পথ যার প্রাথমিক এবং চূড়ান্ত ভার্টেক্স অসংতৃপ্ত, অর্থাৎ, তারা ম্যাচিং-এ অন্তর্গত নয়।

• প্রতিসম পার্থক্য (যাকে বিচ্ছিন্ন সংমিশ্রণও বলা হয়) সেট $A$ এবং $B$ এর, $A \oplus B$ দ্বারা প্রতিনিধিত্ব করা হয়, সমস্ত উপাদানের সেট যা ঠিক $A$ বা $B$ এর একটিতে অন্তর্গত, কিন্তু উভয়েই নয়। অর্থাৎ, $A \oplus B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$।

Berge এর লেম্মা#

এই লেম্মা ফরাসি গণিতবিদ Claude Berge দ্বারা 1957 সালে প্রমাণ করা হয়েছিল, যদিও এটি ইতিমধ্যে ডেনিশ গণিতবিদ Julius Petersen দ্বারা 1891 সালে এবং হাঙ্গেরিয়ান গণিতবিদ Denés Kőnig দ্বারা 1931 সালে পর্যবেক্ষণ করা হয়েছিল।

প্রণয়ন#

একটি ম্যাচিং $M$ সর্বাধিক $\Leftrightarrow$ ম্যাচিং $M$ এর সাপেক্ষে কোনো বর্ধিত পথ নেই।

প্রমাণ#

দ্বি-ইমপ্লিকেশনের উভয় পক্ষ পরোক্ষভাবে প্রমাণ করা হবে।

१। একটি ম্যাচিং $M$ সর্বাধিক $\Rightarrow$ ম্যাচিং $M$ এর সাপেক্ষে কোনো বর্ধিত পথ নেই।

প্রদত্ত সর্বাধিক ম্যাচিং $M$ এর সাপেক্ষে একটি বর্ধিত পথ $P$ রয়েছে বলে ধরুন। এই বর্ধিত পথ $P$ অপরিহার্যভাবে বিজোড় দৈর্ঘ্যের হবে, $M$ এ নেই এমন এক বেশি এজ রয়েছে যা $M$ এতেও আছে এমন এজের সংখ্যার চেয়ে।
আমরা একটি নতুন ম্যাচিং $M'$ তৈরি করি মূল ম্যাচিং $M$ এর সমস্ত এজ অন্তর্ভুক্ত করে যদি তারা $P$ এতেও থাকে তবে ছাড়া, এবং $P$ এর এজ যা $M$ এতে নেই।
এটি একটি বৈধ ম্যাচিং কারণ $P$ এর প্রাথমিক এবং চূড়ান্ত ভার্টেক্স $M$ দ্বারা অসম্পৃক্ত, এবং বাকী ভার্টেক্সগুলি শুধুমাত্র ম্যাচিং $P \cap M$ দ্বারা সম্পৃক্ত।
এই নতুন ম্যাচিং $M'$ $M$ এর চেয়ে একটি বেশি এজ থাকবে, তাই $M$ সর্বাধিক হতে পারে না।

আনুষ্ঠানিকভাবে, একটি বর্ধিত পথ $P$ দেওয়া হলে কিছু সর্বাধিক ম্যাচিং $M$ এর সাপেক্ষে, ম্যাচিং $M' = P \oplus M$ এমন যে $|M'| = |M| + १$, যা একটি বৈপরীত্য।

२। একটি ম্যাচিং $M$ সর্বাধিক $\Leftarrow$ ম্যাচিং $M$ এর সাপেক্ষে কোনো বর্ধিত পথ নেই।

$M$ এর চেয়ে বেশি কার্ডিনালিটির একটি ম্যাচিং $M'$ রয়েছে বলে ধরুন। আমরা প্রতিসম পার্থক্য $Q = M \oplus M'$ বিবেচনা করি। সাবগ্রাফ $Q$ আর অপরিহার্যভাবে একটি ম্যাচিং নয়।
$Q$ তে যেকোনো ভার্টেক্সের সর্বোচ্চ ডিগ্রি २ রয়েছে, যার মানে এতে সমস্ত সংযুক্ত উপাদান তিনটির একটি -

  * একটি বিচ্ছিন্ন ভার্টেক্স
  * একটি (সরল) পথ যার এজগুলি $M$ এবং $M'$ থেকে বিকল্পভাবে আসে
  * একটি সমবর্তী দৈর্ঘ্যের চক্র যার এজগুলি $M$ এবং $M'$ থেকে বিকল্পভাবে আসে

যেহেতু $M'$ $M$ এর চেয়ে বেশি কার্ডিনালিটি রয়েছে, $Q$ এর $M'$ থেকে বেশি এজ আছে $M$ থেকে।
Pigeonhole নীতি দ্বারা, কমপক্ষে একটি সংযুক্ত উপাদান একটি পথ হবে যেটির $M'$ থেকে বেশি এজ আছে $M$ থেকে।
কারণ যেকোনো এই ধরনের পথ পরিবর্তনকারী, এটি প্রাথমিক এবং চূড়ান্ত ভার্টেক্স অসম্পৃক্ত থাকবে $M$ দ্বারা, এটিকে $M$ এর জন্য একটি বর্ধিত পথ করে তোলে,
যা প্রাথমিক অবস্থার সাথে পরস্পরবিরোধী।   $\blacksquare$

কুহনের অ্যালগরিদম#

কুহনের অ্যালগরিদম Berge এর লেম্মার একটি সরাসরি প্রয়োগ। এটি মূলত নিম্নরূপ বর্ণিত:

প্রথমে, আমরা একটি খালি ম্যাচিং নিই। তারপর, যখন অ্যালগরিদম একটি বর্ধিত পথ খুঁজে পেতে সক্ষম হয়, আমরা এই পথ বরাবর বিকল্প করে ম্যাচিং আপডেট করি এবং বর্ধিত পথ খোঁজার প্রক্রিয়া পুনরাবৃত্তি করি। যখনই এই ধরনের পথ খুঁজে পাওয়া সম্ভব নয়, আমরা প্রক্রিয়া থামাই - বর্তমান ম্যাচিং সর্বাধিক।

বর্ধিত পথ খুঁজে পাওয়ার উপায় বিস্তারিত করতে অবশিষ্ট। কুহনের অ্যালগরিদম সহজভাবে এই পথগুলির যেকোনো একটি খোঁজে গভীরতা-প্রথম বা প্রস্থ-প্রথম ট্রাভার্সাল ব্যবহার করে। অ্যালগরিদম গ্রাফের সমস্ত ভার্টেক্স পর্যায়ক্রমে দেখে, প্রতিটি ট্রাভার্সাল এটি থেকে শুরু করে, এই ভার্টেক্স থেকে শুরু হওয়া একটি বর্ধিত পথ খুঁজে পাওয়ার চেষ্টা করে।

অ্যালগরিদম বর্ণনা করা আরও সুবিধাজনক যদি আমরা অনুমান করি যে ইনপুট গ্রাফ ইতিমধ্যে দুটি অংশে বিভক্ত (যদিও, প্রকৃতপক্ষে, অ্যালগরিদম এমনভাবে প্রয়োগ করা যায় যাতে ইনপুট গ্রাফ স্পষ্টভাবে দুটি অংশে বিভক্ত না হয়)।

অ্যালগরিদম গ্রাফের প্রথম অংশের সমস্ত ভার্টেক্স দেখে: $v = १ \ldots n_१$। যদি বর্তমান ভার্টেক্স $v$ ইতিমধ্যে বর্তমান ম্যাচিংয়ের সাথে সম্পৃক্ত (অর্থাৎ, এর সাথে সংলগ্ন কিছু এজ ইতিমধ্যে নির্বাচিত হয়েছে), তবে এই ভার্টেক্স এড়িয়ে যান। অন্যথায়, অ্যালগরিদম এই ভার্টেক্স সম্পৃক্ত করার চেষ্টা করে, যার জন্য এটি এই ভার্টেক্স থেকে শুরু হওয়া একটি বর্ধিত পথ খোঁজার প্রক্রিয়া শুরু করে।

বর্ধিত পথ খোঁজা একটি বিশেষ গভীরতা-প্রথম বা প্রস্থ-প্রথম ট্রাভার্সাল ব্যবহার করে সম্পাদিত হয় (সাধারণত প্রয়োগের সহজতার জন্য গভীরতা-প্রথম ট্রাভার্সাল ব্যবহৃত হয়)। প্রাথমিকভাবে, গভীরতা-প্রথম ট্রাভার্সাল প্রথম অংশের বর্তমান অসম্পৃক্ত ভার্টেক্স $v$ এ রয়েছে। আসুন এই ভার্টেক্স থেকে সমস্ত এজ দেখি। বর্তমান এজ একটি এজ $(v, to)$ হোক। যদি ভার্টেক্স $to$ এখনও ম্যাচিংয়ের সাথে সম্পৃক্ত না হয়, তবে আমরা একটি বর্ধিত পথ খুঁজে পাওয়ার সফল হয়েছি: এটি একটি একক এজ $(v, to)$ নিয়ে গঠিত; এই ক্ষেত্রে, আমরা সহজভাবে এই এজ ম্যাচিংয়ে অন্তর্ভুক্ত করি এবং ভার্টেক্স $v$ থেকে বর্ধিত পথ খোঁজা থামাই। অন্যথায়, যদি $to$ ইতিমধ্যে কিছু এজ $(to, p)$ এর সাথে সম্পৃক্ত হয়, তবে এই এজ বরাবর যাব: এইভাবে আমরা এজ $(v, to),(to, p), \ldots$ এর মাধ্যমে একটি বর্ধিত পথ খুঁজে পাওয়ার চেষ্টা করব। এটি করতে, সহজভাবে আমাদের ট্রাভার্সালে ভার্টেক্স $p$ এ যান - এখন আমরা এই ভার্টেক্স থেকে একটি বর্ধিত পথ খুঁজে পাওয়ার চেষ্টা করি।

তাই, ভার্টেক্স $v$ থেকে শুরু হওয়া এই ট্রাভার্সাল, বা একটি বর্ধিত পথ খুঁজে পাবে, এবং তার দ্বারা ভার্টেক্স $v$ সম্পৃক্ত করবে, বা এই ধরনের একটি বর্ধিত পথ খুঁজে পাবে না (এবং, তাই, এই ভার্টেক্স $v$ সম্পৃক্ত করা যায় না)।

সমস্ত ভার্টেক্স $v = १ \ldots n_१$ পরীক্ষা করা হয়েছে পরে, বর্তমান ম্যাচিং সর্বাধিক হবে।

চলমান সময়#

কুহনের অ্যালগরিদম সম্পূর্ণ গ্রাফে $n$ গভীরতা/প্রস্থ-প্রথম ট্রাভার্সাল রানের একটি সিরিজ হিসাবে চিন্তা করা যেতে পারে। অতএব, সম্পূর্ণ অ্যালগরিদম $O(nm)$ সময়ে সম্পাদিত হয়, সর্বোচ্চ ক্ষেত্রে যা $O(n^३)$ হয়।

তবে, এই অনুমান সামান্য উন্নত করা যায়। দেখা যায় যে কুহনের অ্যালগরিদমের জন্য, কোন অংশ প্রথম এবং কোন দ্বিতীয় হিসাবে নির্বাচিত হয় তা গুরুত্বপূর্ণ। প্রকৃতপক্ষে, উপরে বর্ণিত ইমপ্লিমেন্টেশনে, গভীরতা/প্রস্থ-প্রথম ট্রাভার্সাল শুধুমাত্র প্রথম অংশের ভার্টেক্স থেকে শুরু হয়, তাই সম্পূর্ণ অ্যালগরিদম $O(n_१m)$ সময়ে সম্পাদিত হয়, যেখানে $n_१$ হল প্রথম অংশের ভার্টেক্সের সংখ্যা। সর্বোচ্চ ক্ষেত্রে, এটি $O(n_१ ^ २ n_२)$ (যেখানে $n_२$ হল দ্বিতীয় অংশের ভার্টেক্সের সংখ্যা)। এটি দেখায় যে যখন প্রথম অংশ দ্বিতীয়ের চেয়ে কম ভার্টেক্স থাকে তখন এটি আরও লাভজনক। অত্যন্ত ভারসাম্যহীন গ্রাফে ($n_१$ এবং $n_२$ খুব আলাদা হলে), এটি চলমান সময়ে উল্লেখযোগ্য পার্থক্যে অনুবাদ করে।

ইমপ্লিমেন্টেশন#

স্ট্যান্ডার্ড ইমপ্লিমেন্টেশন#

আসুন এখানে উপরোক্ত অ্যালগরিদমের একটি ইমপ্লিমেন্টেশন উপস্থাপন করি গভীরতা-প্রথম ট্রাভার্সালের উপর ভিত্তি করে এবং একটি দ্বিপার্শ্বিক গ্রাফ গ্রহণ করে দুটি অংশে স্পষ্টভাবে বিভক্ত একটি গ্রাফের আকারে। এই ইমপ্লিমেন্টেশন অত্যন্ত সংক্ষিপ্ত, এবং সম্ভবত এটি এই রূপে মনে রাখা উচিত।

এখানে $n$ হল প্রথম অংশে ভার্টেক্সের সংখ্যা, $k$ - দ্বিতীয় অংশে, $g[v]$ হল প্রথম অংশের শীর্ষ থেকে এজের তালিকা (অর্থাৎ সংখ্যার তালিকা যা এজ $v$ থেকে নিয়ে যায়)। উভয় অংশের ভার্টেক্সগুলি স্বাধীনভাবে সংখ্যায়িত, অর্থাৎ প্রথম অংশের ভার্টেক্সগুলি $१ \ldots n$ দ্বারা সংখ্যায়িত, এবং দ্বিতীয়টিতে $१ \ldots k$ দ্বারা সংখ্যায়িত।

তারপর দুটি সহায়ক অ্যারে রয়েছে: $\rm mt$ এবং $\rm used$। প্রথম - $\rm mt$ - বর্তমান ম্যাচিং সম্পর্কিত তথ্য ধারণ করে। প্রোগ্রামিংয়ের সুবিধার জন্য, এই তথ্য শুধুমাত্র দ্বিতীয় অংশের ভার্টেক্সের জন্য অন্তর্ভুক্ত: $\textrm{mt[} i \rm]$ - এটি প্রথম অংশের ভার্টেক্সের সংখ্যা যা দ্বিতীয় অংশের ভার্টেক্স $i$ এর সাথে একটি এজ দ্বারা সংযুক্ত (বা $-१$, যদি এটি থেকে কোনো ম্যাচিং এজ বের না হয়)। দ্বিতীয় অ্যারে হল $\rm used$: গভীরতা-প্রথম ট্রাভার্সালে ভার্টেক্সে “পরিদর্শন” এর সাধারণ অ্যারে (এটি শুধুমাত্র প্রয়োজন যাতে গভীরতা-প্রথম ট্রাভার্সাল একই ভার্টেক্সে দুইবার প্রবেশ না করে)।

একটি ফাংশন $\textrm{try_kuhn}$ একটি গভীরতা-প্রথম ট্রাভার্সাল। এটি $\rm true$ রিটার্ন করে যদি এটি ভার্টেক্স $v$ থেকে একটি বর্ধিত পথ খুঁজে পেতে সক্ষম হয়েছে, এবং এটি বিবেচনা করা হয় যে এই ফাংশন ইতিমধ্যে খুঁজে পাওয়া শৃঙ্খল বরাবর ম্যাচিংয়ের বিকল্প সম্পাদন করেছে।

ফাংশনের মধ্যে, প্রথম অংশের ভার্টেক্স $v$ থেকে বের হওয়া সমস্ত এজ স্ক্যান করা হয়, এবং তারপর নিম্নোক্তটি পরীক্ষা করা হয়: যদি এই এজ একটি অসম্পৃক্ত ভার্টেক্স $to$ এর দিকে নিয়ে যায়, বা যদি এই ভার্টেক্স $to$ সম্পৃক্ত হয়, তবে এটি $\textrm{mt[}to \rm ]$ থেকে রিকার্সিভভাবে শুরু করে একটি ক্রমবর্ধমান শৃঙ্খল খুঁজে পাওয়া সম্ভব, তবে আমরা বলি যে আমরা একটি বর্ধিত পথ খুঁজে পেয়েছি, এবং ফলাফল $\rm true$ সহ ফাংশন থেকে রিটার্ন করার আগে, আমরা বর্তমান এজ বিকল্প করি: আমরা $to$ এর সাথে সংলগ্ন এজ ভার্টেক্স $v$ এর দিকে পুনর্নির্দেশ করি।

প্রধান প্রোগ্রাম প্রথমে নির্দেশ করে যে বর্তমান ম্যাচিং খালি (তালিকা $\rm mt$ সংখ্যা $-१$ দিয়ে পূর্ণ)। তারপর প্রথম অংশের ভার্টেক্স $v$ $\textrm{try_kuhn}$ দ্বারা অনুসন্ধান করা হয়, এবং এটি থেকে গভীরতা-প্রথম ট্রাভার্সাল শুরু করা হয়, আগে থেকেই অ্যারে $\rm used$ সেট করা হয়েছে।

এটি উল্লেখযোগ্য যে ম্যাচিংয়ের আকার সহজেই পাওয়া যায় প্রধান প্রোগ্রামে $\textrm{try_kuhn}$ এর কল সংখ্যা হিসাবে যা ফলাফল $\rm true$ রিটার্ন করেছে। পছন্দসই সর্বাধিক ম্যাচিং নিজেই অ্যারে $\rm mt$ তে অন্তর্ভুক্ত।

int n, k;
vector<vector<int>> g;
vector<int> mt;
vector<bool> used;

bool try_kuhn(int v) {
    if (used[v])
        return false;
    used[v] = true;
    for (int to : g[v]) {
        if (mt[to] == -1 || try_kuhn(mt[to])) {
            mt[to] = v;
            return true;
        }
    }
    return false;
}

int main() {
    //... reading the graph ...

    mt.assign(k, -1);
    for (int v = 0; v < n; ++v) {
        used.assign(n, false);
        try_kuhn(v);
    }

    for (int i = 0; i < k; ++i)
        if (mt[i] != -1)
            printf("%d %d\n", mt[i] + 1, i + 1);
}

We repeat once again that Kuhn’s algorithm is easy to implement in such a way that it works on graphs that are known to be bipartite, but their explicit splitting into two parts has not been given. In this case, it will be necessary to abandon the convenient division into two parts, and store all the information for all vertices of the graph. For this, an array of lists $g$ is now specified not only for the vertices of the first part, but for all the vertices of the graph (of course, now the vertices of both parts are numbered in a common numbering - from $1$ to $n$). Arrays $\rm mt$ and are $\rm used$ are now also defined for the vertices of both parts, and, accordingly, they need to be kept in this state.

উন্নত ইমপ্লিমেন্টেশন#

আসুন অ্যালগরিদম নিম্নরূপ পরিবর্তন করি। অ্যালগরিদমের প্রধান লুপের আগে, আমরা কিছু সাধারণ অ্যালগরিদম দ্বারা একটি স্বেচ্ছাচারী ম্যাচিং খুঁজে পাব (একটি সাধারণ হিউরিস্টিক অ্যালগরিদম), এবং শুধুমাত্র তারপর আমরা $\textrm{try_kuhn}()$ ফাংশনের কল সহ একটি লুপ সম্পাদন করব, যা এই ম্যাচিং উন্নত করবে। ফলস্বরূপ, অ্যালগরিদম র্যান্ডম গ্রাফে উল্লেখযোগ্যভাবে দ্রুত কাজ করবে - কারণ বেশিরভাগ গ্রাফে, আপনি সহজেই হিউরিস্টিক ব্যবহার করে যথেষ্ট বড় আকারের একটি ম্যাচিং খুঁজে পেতে পারেন, এবং তারপর সাধারণ কুহনের অ্যালগরিদম ব্যবহার করে খুঁজে পাওয়া ম্যাচিংকে সর্বাধিকে উন্নত করুন। এভাবে, আমরা সেই ভার্টেক্স থেকে গভীরতা-প্রথম ট্রাভার্সাল চালু করতে সংরক্ষণ করব যা আমরা ইতিমধ্যে হিউরিস্টিক ব্যবহার করে বর্তমান ম্যাচিংয়ে অন্তর্ভুক্ত করেছি।

উদাহরণস্বরূপ, আপনি সহজভাবে প্রথম অংশের সমস্ত ভার্টেক্সের উপর পুনরাবৃত্তি করতে পারেন, এবং প্রতিটির জন্য, ম্যাচিংয়ে যোগ করা যেতে পারে এমন একটি স্বেচ্ছাচারী এজ খুঁজে পান এবং এটি যোগ করুন। এমনকি এই ধরনের সাধারণ হিউরিস্টিক কুহনের অ্যালগরিদম কয়েকগুণ গতি দিতে পারে।

মনে রাখবেন যে প্রধান লুপ সামান্য পরিবর্তন করতে হবে। যেহেতু প্রধান লুপে $\textrm{try_kuhn}$ ফাংশন ডাকার সময়, অনুমান করা হয় যে বর্তমান ভার্টেক্স এখনও ম্যাচিংয়ে অন্তর্ভুক্ত নয়, আপনাকে একটি উপযুক্ত চেক যোগ করতে হবে।

ইমপ্লিমেন্টেশনে, শুধুমাত্র $\textrm{main}()$ ফাংশনে কোড পরিবর্তিত হবে:

int main() {
    // ... reading the graph ...

    mt.assign(k, -1);
    vector<bool> used1(n, false);
    for (int v = 0; v < n; ++v) {
        for (int to : g[v]) {
            if (mt[to] == -1) {
                mt[to] = v;
                used1[v] = true;
                break;
            }
        }
    }
    for (int v = 0; v < n; ++v) {
        if (used1[v])
            continue;
        used.assign(n, false);
        try_kuhn(v);
    }

    for (int i = 0; i < k; ++i)
        if (mt[i] != -1)
            printf("%d %d\n", mt[i] + 1, i + 1);
}

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

নোট#

• কুহনের অ্যালগরিদম Hungarian অ্যালগরিদম এর একটি সাবরুটিন, যা Kuhn-Munkres অ্যালগরিদম নামেও পরিচিত।
• কুহনের অ্যালগরিদম $O(nm)$ সময়ে চলে। এটি সাধারণত প্রয়োগ করা সহজ, তবে সর্বাধিক দ্বিপার্শ্বিক ম্যাচিং সমস্যার জন্য আরও দক্ষ অ্যালগরিদম বিদ্যমান - যেমন Hopcroft-Karp-Karzanov অ্যালগরিদম, যা $O(\sqrt{n}m)$ সময়ে চলে।
• ন্যূনতম শীর্ষ কভার সমস্যা সাধারণ গ্রাফের জন্য NP-কঠিন। তবে, Kőnig এর উপপাদ্য দেয় যে দ্বিপার্শ্বিক গ্রাফের জন্য, সর্বাধিক ম্যাচিংয়ের কার্ডিনালিটি ন্যূনতম শীর্ষ কভারের কার্ডিনালিটির সমান। সুতরাং, আমরা সর্বাধিক দ্বিপার্শ্বিক ম্যাচিং অ্যালগরিদম ব্যবহার করে দ্বিপার্শ্বিক গ্রাফের জন্য বহুপদ সময়ে ন্যূনতম শীর্ষ কভার সমস্যা সমাধান করতে পারি।

অনুশীলন সমস্যা#

• Kattis - Gopher II
• Kattis - Borders