الگوریتم Kuhn برای تطابق بیشینه در گراف دو بخشی¶
مسئله¶
یک گراف دوبخشی $G$ با $n$ رأس و $m$ یال به شما داده شده است. تطابق بیشینه را پیدا کنید، یعنی بیشترین تعداد یال ممکن را طوری انتخاب کنید که هیچ دو یالِ انتخاب‌شده‌ای رأس مشترک نداشته باشند.
توصیف الگوریتم¶
تعاریف مورد نیاز¶
-
یک تطابق (matching) $M$ مجموعه‌ای از یال‌های دوبه‌دو غیرمجاور یک گراف است (به عبارت دیگر، از هر رأس گراف $M$ نباید بیش از یک یال از این مجموعه به آن متصل باشد). اندازه (cardinality) یک تطابق تعداد یال‌های موجود در آن است. تمام رأس‌هایی که یک یال مجاور از تطابق دارند (یعنی در زیرگراف تشکیل‌شده توسط $M$ درجه‌ای دقیقاً برابر با یک دارند)، اشباع‌شده (saturated) توسط این تطابق نامیده می‌شوند.
-
یک تطابق ماکسیمال (maximal matching) تطابق $M$ از گراف $G$ است که زیرمجموعه‌ی هیچ تطابق دیگری نباشد.
-
یک تطابق بیشینه (maximum matching) (که به آن تطابق با بیشترین اندازه نیز گفته می‌شود) تطابقی است که بیشترین تعداد ممکن یال را در خود جای داده است. هر تطابق بیشینه، یک تطابق ماکسیمال است.
-
یک مسیر (path) به طول $k$ در اینجا به معنای یک مسیر ساده است (یعنی شامل رأس‌ها یا یال‌های تکراری نیست) که شامل $k$ یال است، مگر اینکه خلاف آن ذکر شود.
-
یک مسیر متناوب (alternating path) (در یک گراف دو بخشی، نسبت به یک تطابق خاص) مسیری است که یال‌های آن به طور متناوب به تطابق تعلق دارند / ندارند.
-
یک مسیر افزایشی (augmenting path) (در یک گراف دو بخشی، نسبت به یک تطابق خاص) یک مسیر متناوب است که رأس‌های ابتدایی و انتهایی آن اشباع‌نشده (unsaturated) هستند، یعنی به تطابق تعلق ندارند.
-
تفاضل متقارن (symmetric difference) (که به آن اجتماع فصلی (disjunctive union) نیز گفته می‌شود) مجموعه‌های $A$ و $B$ که با $A \oplus B$ نمایش داده می‌شود، مجموعه‌ای از تمام عناصری است که دقیقاً به یکی از مجموعه‌های $A$ یا $B$ تعلق دارند، اما نه به هر دو. یعنی $A \oplus B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$.
لم برژ¶
این لم توسط ریاضیدان فرانسوی کلود برژ (Claude Berge) در سال ۱۹۵۷ اثبات شد، اگرچه پیش از آن توسط ریاضیدان دانمارکی یولیوس پترسن (Julius Petersen) در سال ۱۸۹۱ و ریاضیدان مجار دنش کونیگ (Denés Kőnig) در سال ۱۹۳۱ مشاهده شده بود.
فرمول‌بندی¶
یک تطابق $M$ بیشینه است $\Leftrightarrow$ هیچ مسیر افزایشی نسبت به تطابق $M$ وجود نداشته باشد.
اثبات¶
هر دو طرف این گزاره دوشرطی با برهان خلف اثبات خواهند شد.
-
یک تطابق $M$ بیشینه است $\Rightarrow$ هیچ مسیر افزایشی نسبت به تطابق $M$ وجود ندارد.
فرض کنید یک مسیر افزایشی $P$ نسبت به تطابق بیشینه داده‌شده $M$ وجود دارد. این مسیر افزایشی $P$ لزوماً طولی فرد خواهد داشت و تعداد یال‌های آن که در $M$ نیستند، یکی بیشتر از تعداد یال‌هایی است که در $M$ نیز هستند. ما یک تطابق جدید $M'$ با گنجاندن تمام یال‌های تطابق اصلی $M$ به جز آن‌هایی که در $P$ نیز هستند، و یال‌های موجود در $P$ که در $M$ نیستند، ایجاد می‌کنیم. این یک تطابق معتبر است زیرا رأس‌های ابتدایی و انتهایی $P$ توسط $M$ اشباع نشده‌اند و بقیه رأس‌ها فقط توسط تطابق $P \cap M$ اشباع شده‌اند. این تطابق جدید $M'$ یک یال بیشتر از $M$ خواهد داشت و بنابراین $M$ نمی‌توانسته بیشینه باشد.
به طور رسمی، با فرض وجود یک مسیر افزایشی $P$ نسبت به یک تطابق بیشینه $M$، تطابق $M' = P \oplus M$ طوری است که $|M'| = |M| + 1$ که یک تناقض است.
-
یک تطابق $M$ بیشینه است $\Leftarrow$ هیچ مسیر افزایشی نسبت به تطابق $M$ وجود ندارد.
فرض کنید تطابق $M'$ با اندازه‌ای بزرگتر از $M$ وجود دارد. تفاضل متقارن $Q = M \oplus M'$ را در نظر می‌گیریم. زیرگراف $Q$ لزوماً دیگر یک تطابق نیست. هر رأس در $Q$ حداکثر درجه ۲ دارد، به این معنی که تمام مؤلفه‌های همبند در آن یکی از این سه حالت هستند -
- یک رأس جدا افتاده
- یک مسیر (ساده) که یال‌های آن به طور متناوب از $M$ و $M'$ هستند
- یک دور با طول زوج که یال‌های آن به طور متناوب از $M$ و $M'$ هستند
از آنجایی که اندازه $M'$ بزرگتر از $M$ است، $Q$ یال‌های بیشتری از $M'$ نسبت به $M$ دارد. طبق اصل لانه کبوتری، حداقل یک مؤلفه همبند، مسیری خواهد بود که یال‌های بیشتری از $M'$ نسبت به $M$ دارد. از آنجا که هر چنین مسیری متناوب است، رأس‌های ابتدایی و انتهایی آن توسط $M$ اشباع نشده خواهند بود، که آن را به یک مسیر افزایشی برای $M$ تبدیل می‌کند، و این با فرض اولیه در تناقض است. $\blacksquare$
الگوریتم Kuhn¶
الگوریتم Kuhn یک کاربرد مستقیم از لم برژ است. اساساً به شرح زیر توصیف می‌شود:
ابتدا، یک تطابق خالی در نظر می‌گیریم. سپس، تا زمانی که الگوریتم قادر به یافتن یک مسیر افزایشی باشد، تطابق را با جایگزینی یال‌ها در طول این مسیر به‌روزرسانی می‌کنیم و فرآیند یافتن مسیر افزایشی را تکرار می‌کنیم. به محض اینکه دیگر امکان یافتن چنین مسیری وجود نداشته باشد، فرآیند را متوقف می‌کنیم - تطابق فعلی، تطابق بیشینه است.
باقی می‌ماند که روش یافتن مسیرهای افزایشی را تشریح کنیم. الگوریتم Kuhn به سادگی با استفاده از پیمایش اول-عمق یا اول-سطح به دنبال هر یک از این مسیرها می‌گردد. الگوریتم به نوبت تمام رأس‌های گراف را بررسی می‌کند و هر پیمایش را از یکی از آنها شروع می‌کند تا یک مسیر افزایشی را که از این رأس شروع می‌شود، پیدا کند.
توصیف الگوریتم راحت‌تر است اگر فرض کنیم که گراف ورودی از قبل به دو بخش تقسیم شده است (اگرچه در واقع، الگوریتم را می‌توان به گونه‌ای پیاده‌سازی کرد که گراف ورودی به صراحت به دو بخش تقسیم نشده باشد).
الگوریتم تمام رئوس $v$ بخش اول گراف را بررسی می‌کند: $v = 1 \ldots n_1$. اگر رأس فعلی $v$ قبلاً با تطابق فعلی اشباع شده باشد (یعنی یالی مجاور آن قبلاً انتخاب شده باشد)، آنگاه از این رأس صرف نظر می‌شود. در غیر این صورت، الگوریتم سعی می‌کند این رأس را اشباع کند، که برای این کار جستجویی برای یافتن یک مسیر افزایشی را از این رأس شروع می‌کند.
جستجوی مسیر افزایشی با استفاده از یک پیمایش خاص اول-عمق یا اول-سطح انجام می‌شود (معمولاً برای سهولت پیاده‌سازی از پیمایش اول-عمق استفاده می‌شود). در ابتدا، پیمایش اول-عمق در رأس اشباع‌نشده فعلی $v$ از بخش اول قرار دارد. بیایید تمام یال‌های خروجی از این رأس را بررسی کنیم. فرض کنید یال فعلی، یال $(v, to)$ باشد. اگر رأس $to$ هنوز با تطابق اشباع نشده باشد، ما موفق به یافتن یک مسیر افزایشی شده‌ایم: این مسیر از یک یال منفرد $(v, to)$ تشکیل شده است؛ در این حالت، به سادگی این یال را به تطابق اضافه می‌کنیم و جستجو برای مسیر افزایشی از رأس $v$ را متوقف می‌کنیم. در غیر این صورت، اگر $to$ قبلاً با یالی مانند $(to, p)$ اشباع شده باشد، ما در امتداد این یال پیش می‌رویم: به این ترتیب سعی می‌کنیم یک مسیر افزایشی پیدا کنیم که از یال‌های $(v, to),(to, p), \ldots$ عبور می‌کند. برای انجام این کار، به سادگی در پیمایش خود به رأس $p$ می‌رویم - اکنون سعی می‌کنیم یک مسیر افزایشی از این رأس پیدا کنیم.
بنابراین، این پیمایش که از رأس $v$ شروع شده است، یا یک مسیر افزایشی پیدا می‌کند و در نتیجه رأس $v$ را اشباع می‌کند، یا چنین مسیر افزایشی را پیدا نمی‌کند (و در نتیجه، این رأس $v$ نمی‌تواند اشباع شود).
پس از اینکه تمام رئوس $v = 1 \ldots n_1$ بررسی شدند، تطابق فعلی بیشینه خواهد بود.
زمان اجرا¶
می‌توان الگوریتم Kuhn را به عنوان یک سری از $n$ اجرای پیمایش اول-عمق/اول-سطح روی کل گراف در نظر گرفت. بنابراین، کل الگوریتم در زمان $O(nm)$ اجرا می‌شود که در بدترین حالت $O(n^3)$ است.
با این حال، این تخمین را می‌توان کمی بهبود بخشید. معلوم می‌شود که برای الگوریتم Kuhn، مهم است که کدام بخش از گراف به عنوان بخش اول و کدام به عنوان بخش دوم انتخاب شود. در واقع، در پیاده‌سازی شرح داده شده در بالا، پیمایش اول-عمق/اول-سطح فقط از رئوس بخش اول شروع می‌شود، بنابراین کل الگوریتم در زمان $O(n_1m)$ اجرا می‌شود، که در آن $n_1$ تعداد رئوس بخش اول است. در بدترین حالت، این مقدار $O(n_1 ^ 2 n_2)$ است (که در آن $n_2$ تعداد رئوس بخش دوم است). این نشان می‌دهد که وقتی بخش اول رأس‌های کمتری نسبت به بخش دوم دارد، سودمندتر است. در گراف‌های بسیار نامتعادل (وقتی $n_1$ و $n_2$ بسیار متفاوت هستند)، این امر به تفاوت قابل توجهی در زمان اجرا منجر می‌شود.
پیاده‌سازی¶
پیاده‌سازی استاندارد¶
در اینجا پیاده‌سازی الگوریتم فوق را بر اساس پیمایش اول-عمق ارائه می‌دهیم که یک گراف دو بخشی را به صورت گرافی که به صراحت به دو بخش تقسیم شده است، می‌پذیرد. این پیاده‌سازی بسیار مختصر است و شاید بهتر باشد آن را به همین شکل به خاطر بسپارید.
در اینجا $n$ تعداد رئوس در بخش اول، $k$ در بخش دوم است، $g[v]$ لیست یال‌های رأس $v$ از بخش اول است (یعنی لیست شماره رئوسی که این یال‌ها از $v$ به آنها می‌روند). رئوس در هر دو بخش به طور مستقل شماره‌گذاری شده‌اند، یعنی رئوس در بخش اول از $1 \ldots n$ و در بخش دوم از $1 \ldots k$ شماره‌گذاری شده‌اند.
سپس دو آرایه کمکی وجود دارد: $\rm mt$ و $\rm used$. اولی - $\rm mt$ - اطلاعات تطابق فعلی را در خود دارد. برای راحتی برنامه‌نویسی، این اطلاعات فقط برای رئوس بخش دوم نگهداری می‌شود: $\textrm{mt[} i \rm]$ شماره رأس بخش اول است که با یالی به رأس $i$ از بخش دوم متصل است (یا ۱- اگر هیچ یال تطابقی از آن خارج نشود). آرایه دوم $\rm used$ است: آرایه معمول "بازدید شده‌ها" برای رئوس در پیمایش اول-عمق (این آرایه فقط برای این لازم است که پیمایش اول-عمق دو بار وارد یک رأس نشود).
تابع $\textrm{try_kuhn}$ یک پیمایش اول-عمق است. اگر موفق به یافتن یک مسیر افزایشی از رأس v شود، true برمی‌گرداند و فرض بر این است که این تابع قبلاً جایگزینی تطابق در طول زنجیره یافت‌شده را انجام داده است.
درون تابع، تمام یال‌های خروجی از رأس $v$ بخش اول پیمایش می‌شوند و سپس موارد زیر بررسی می‌شود: اگر این یال به یک رأس اشباع‌نشده $to$ منتهی شود، یا اگر این رأس $to$ اشباع شده باشد اما بتوان با شروع بازگشتی از $\textrm{mt[}to \rm ]$ یک زنجیره افزایشی پیدا کرد، آنگاه می‌گوییم که یک مسیر افزایشی پیدا کرده‌ایم و قبل از بازگشت از تابع با نتیجه true، یال فعلی را جایگزین می‌کنیم: یال مجاور به $to$ را به رأس $v$ هدایت می‌کنیم.
برنامه اصلی ابتدا مشخص می‌کند که تطابق فعلی خالی است (لیست mt با اعداد ۱- پر می‌شود). سپس رأس $v$ از بخش اول توسط try_kuhn جستجو می‌شود و یک پیمایش اول-عمق از آن شروع می‌شود، در حالی که قبلاً آرایه used صفر شده است.
شایان ذکر است که اندازه تطابق به راحتی به عنوان تعداد فراخوانی‌های try_kuhn در برنامه اصلی که نتیجه true را برگردانده‌اند، به دست می‌آید. خود تطابق بیشینه مورد نظر در آرایه 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() {
//... خواندن گراف ...
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);
}
یک بار دیگر تکرار می‌کنیم که الگوریتم Kuhn را می‌توان به راحتی طوری پیاده‌سازی کرد که روی گراف‌هایی که دو بخشی بودن آنها مشخص است اما تقسیم‌بندی صریح آنها به دو بخش داده نشده، کار کند. در این حالت، لازم است از تقسیم‌بندی راحت به دو بخش صرف‌نظر کرده و تمام اطلاعات را برای تمام رئوس گراف ذخیره کنیم. برای این منظور، یک آرایه از لیست‌های $g$ نه تنها برای رئوس بخش اول، بلکه برای تمام رئوس گراف مشخص می‌شود (البته، اکنون رئوس هر دو بخش در یک شماره‌گذاری مشترک - از ۱ تا $n$ - شماره‌گذاری می‌شوند). آرایه‌های mt و used نیز اکنون برای رئوس هر دو بخش تعریف شده و بر این اساس، باید در این حالت نگهداری شوند.
پیاده‌سازی بهبودیافته¶
بیایید الگوریتم را به شرح زیر اصلاح کنیم. قبل از حلقه اصلی الگوریتم، یک تطابق دلخواه با استفاده از یک الگوریتم ساده (یک الگوریتم هیوریستیک ساده) پیدا می‌کنیم و تنها پس از آن حلقه را با فراخوانی‌های تابع try_kuhn() که این تطابق را بهبود می‌بخشد، اجرا می‌کنیم. در نتیجه، الگوریتم روی گراف‌های تصادفی به طور قابل ملاحظه‌ای سریع‌تر عمل خواهد کرد - زیرا در اکثر گراف‌ها، می‌توان به راحتی با استفاده از هیوریستیک، یک تطابق با اندازه به اندازه کافی بزرگ پیدا کرد و سپس تطابق یافت‌شده را با استفاده از الگوریتم معمول Kuhn به تطابق بیشینه بهبود داد. به این ترتیب، ما در اجرای پیمایش اول-عمق از آن رأس‌هایی که قبلاً با استفاده از هیوریستیک در تطابق فعلی گنجانده‌ایم، صرفه‌جویی خواهیم کرد.
به عنوان مثال، می‌توانید به سادگی روی تمام رئوس بخش اول پیمایش کنید و برای هر کدام، یک یال دلخواه پیدا کنید که بتوان به تطابق اضافه کرد و آن را اضافه کنید. حتی چنین هیوریستیک ساده‌ای می‌تواند الگوریتم Kuhn را چندین برابر سریع‌تر کند.
لطفاً توجه داشته باشید که حلقه اصلی باید کمی تغییر کند. از آنجایی که هنگام فراخوانی تابع try_kuhn در حلقه اصلی، فرض بر این است که رأس فعلی هنوز در تطابق گنجانده نشده است، باید یک بررسی مناسب اضافه کنید.
در پیاده‌سازی، فقط کد درون تابع main() تغییر خواهد کرد:
int main() {
// ... خواندن گراف ...
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);
}
یک هیوریستیک خوب دیگر به شرح زیر است. در هر مرحله، به دنبال رأس با کمترین درجه (اما نه ایزوله) می‌گردد، هر یالی از آن را انتخاب کرده و به تطابق اضافه می‌کند، سپس هر دو رأس این یال را به همراه تمام یال‌های متصل به آنها از گراف حذف می‌کند. چنین روش حریصانه‌ای روی گراف‌های تصادفی بسیار خوب عمل می‌کند؛ در بسیاری از موارد حتی تطابق بیشینه را می‌سازد (اگرچه یک نمونه تست علیه آن وجود دارد که روی آن تطابقی بسیار کوچکتر از تطابق بیشینه پیدا می‌کند).
نکات¶
- الگوریتم Kuhn یک زیرروال در الگوریتم مجارستانی (Hungarian algorithm) است که به آن الگوریتم Kuhn-Munkres نیز گفته می‌شود.
- الگوریتم Kuhn در زمان $O(nm)$ اجرا می‌شود. پیاده‌سازی آن به طور کلی ساده است، با این حال، الگوریتم‌های کارآمدتری برای مسئله تطابق بیشینه در گراف دو بخشی وجود دارد - مانند الگوریتم Hopcroft-Karp-Karzanov که در زمان $O(\sqrt{n}m)$ اجرا می‌شود.
- مسئله پوشش رأسی کمینه برای گراف‌های عمومی NP-سخت است. با این حال، قضیه کونیگ بیان می‌کند که برای گراف‌های دو بخشی، اندازه تطابق بیشینه برابر با اندازه پوشش رأسی کمینه است. از این رو، می‌توانیم از الگوریتم‌های تطابق بیشینه دو بخشی برای حل مسئله پوشش رأسی کمینه در زمان چندجمله‌ای برای گراف‌های دو بخشی استفاده کنیم.