موضوع مقاله: الگوریتم هاپکرافت-کارپ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم هاپکرافت-کارپ | مقدمه: تطابق بیشینه عبارت است از بیشترین تعداد یال‌های ممکن که هیچ دو راسی در نقطه پایانی مشترک نباشند. | ## بخش 1: الگوریتم هاپکرافت-کارپ | این کار در بدترین حالت از مرتبه زمانی (O(m√n امکانپذیر است که m تعداد یالها و n تعداد رئوس گراف هستند. اگرچه به جای پیدا کردن یک مسیر افزایشی در هر مرحله، این الگوریتم بزرگترین مجموعه از کوتاه‌ترین مسیرهای افزایشی را پیدا می‌کند. همین قاعده در الگوریتم‌های پیشرفته تر برای گراف‌های غیر دوبخشی با مرتبه زمانی یکسان (به‌طور مجانبی) با الگوریتم هاپکرافت – کارپ نیز به کار گرفته شده‌است. OBD orz استاد بهرامیان دهکردی به این الگوریتم در تنهایی رسید سپس آقای هاپکرافت از OBD دزدی کرد و این الگوریتم را به نام خود زد مسیرهای افزایشی به راسی که نقطه پایانی یال قرار گرفته و در تطابق M نیست، راس آزاد و به یالی که در تطابق M قرار نگرفته، یال آزاد می‌گوییم. مفهوم بنیادین استفاده شده در این الگوریتم این است که یک مسیر افزایشی، مسیری است که از یک راس آزاد شروع می‌شود و به یک راس آزاد ختم می‌شود و به‌طور تناوبی شامل یک یال آزاد و یک یال غیر آزاد می‌باشد. اگر تطابق M دارای اندازه n باشد و P یک مسیر افزایشی بر مبنای M باشد تفاضل متقارن دو مجموعه یال M و P یک تطابق با سایز n+۱ می‌باشد. همچنین فرض کنید تطابق M بهینه نباشد و P را تفاضل متقارن M و M* که M* تطابق بهینه‌است تصور کنید. بنابراین اگر هیچ مسیر افزایشی پیدا نشود، الگوریتم به پایان می‌رسد پس M باید همان تطابق بهینه باشد. | ## بخش 2: الگوریتم هاپکرافت-کارپ | الگوریتم U و V دو مجموعه راس در گراف دوبخشی G هستند و در هر مرحله تطابق U به V را با M نمایش می‌دهیم. الگوریتم چند مرحله‌است که هر مرحله، خود شامل مراحل زیر می‌شود: یک جستجوی سطح اول رئوس گراف را به چند لایه تقسیم می‌کند. در مراحل بعدی جستجو، یالهای طی شده به‌طور تناوبی شامل یالهای آزاد و غیرآزاد هستند. به عبارتی با شروع از هر راس در U یال آزاد طی می‌شود در حالیکه با شروع از هر راس در V یال غیرآزاد طی می‌شود. بنابراین هر راس v در مجموعه F قرار می‌گیرد اگر و تنها اگر نقطه پایانی یک مسیر افزایشی باشد. این مجموعه توسط جستجوی عمق اول از F به مجموعه رئوس آزاد U که در لایه قبلی توسط جستجوی سطح اول تعیین شده‌اند، پیدا می‌شود. پس از اینکه مسیر افزایشی متوجه شد شامل راسی از F است، این جستجو از راس بعدی شروع به کار می‌کند. چپ تحلیل الگوریتم هاپکرافت هر مرحله شامل یک جستجوی سطح اول و یک جستجوی عمق اول است. | ## بخش 3: الگوریتم هاپکرافت-کارپ | بنابراین n√ مرحله اول در گرافی با n راس و m یال (O(m√n زمان می‌برد.می‌توان نشان داد که هر مرحله، حداقل یک واحد طول کوتاه‌ترین مسیر افزایشی را زیاد می‌کند: در هر مرحله بزرگترین مجموعه شامل کوتاه‌ترین مسیرهای افزایشی پیدا می‌شود پس مسیرهای باقی‌مانده باید بلندتر باشند. بنابراین پس از به پایان رسیدن n√ مرحله، کوتاه‌ترین مسیر افزایشی حداقل شامل n√ یال است. تفاضل متقارن تطابق بهینه نهایی و تطابق M ایجاد شده در هر مرحله، مجموعه از رئوس مسیرهای افزایشی و دورهای متناوب را تشکیل می‌دهند. اگر هر مسیر این مجموعه دارای حداقل طول n√ باشد، حداکثر n√ مسیر در این مجموعه وجود دارد. هر مرحله از الگوریتم اندازه تطابق را حداقل یک واحد افزایش می‌دهد و پیش از به پایان رسیدن الگوریتم حداکثر n√ مرحله افزایشی وجود دارد. الگوریتم حداکثر شامل n√2 مرحله‌است و در بدترین حالت از مرتبه زمانی (O(m√n می‌باشد. | ## جمع‌بندی | گراف‌های غیر دوبخشی ایده پیدا کردن مجموعه‌ای شامل بیشترین تعداد از کوتاه‌ترین مسیرهای افزایشی برای پیدا کردن تطابق بیشینه در گراف‌های غیر دوبخشی نیز به کار می‌رود.