این درس شامل موارد زیر است:

• تعاریف
• مقدمه
• قضیه ۱
• الگوریتم
• تحلیل
• منبع

• گراف دوبخشی: گرافی است که راس‌هایش را بتوان به دو مجموعه‌ افراز کرد، به طوری که برای هر یالِ uv، u و v در دو مجموعه‌ی متفاوت باشند.
• تطابق: یک تطابق در گراف بدون جهت G عبارت است از مجموعه‌ای از یال‌های گراف به طوری که هر رأس حداکثر به یکی از یال‌های مجموعه متصل باشد. رأس‌ی که به یکی از یال‌های تطابق متصل باشد را «آلوده» می‌نامیم. اگر یک تطابق تمام رئوس گراف را آلوده کند، آن تطابق را یک «تطابق کامل» می‌نامیم.
• تطابق ماکسیمم: تطابقی است که تعداد یال‌های آن از هر تطابق دیگری در آن گراف بیشتر یا مساوی باشد. هم‌چنین تطابق ماکسیمال تطابقی است که نتوان یالی از یال‌های گراف را به آن اضافه کرد به طوری که یک تطابق بزرگتر بوجود بیاید. بدیهی است که یک تطابق ماکسیمال ممکن است ماکسیمم نباشد.
• مسیر افزایشی: یک مسیر متناوب مسیری است که یال‌هایش یکی در میان در تطابق قرار داشته باشند. یک مسیر متناوب که رئوس اول و آخر آن در تطابق نباشند را یک مسیر افزایشی می گویند.

در مجموعه‌ای از اشیا هر شی می‌تواند با برخی از اشیای دیگر سازگار باشد. مثلاً در مجموعه‌ای از آدم ها افراد می‌توانند با یکدیگر دوست باشند در نتیجه می توان دوستی را یک رابطه سازگاری تعریف کرد. حال فرض کنید بخواهیم این گروه را به مجموعه‌هایی دوتایی تقسیم کنیم که هر فرد حداکثر در یک گروه بیاید و افراد هر گروه با یکدیگر دوست باشند. در واقع مسائلی از این قبیل را می‌توان به دید گراف و پیدا کردن یک تطابق ماکسیمم در این گراف نگاه کرد. با افزایش سؤالاتی از این قبیل دغدغه‌ای برای پیدا کردن یک الگوریتم مناسب برای حل این گونه مسائل در افراد بوجود آمد. از اولین قضیا در این مجموعه که برای پیدا کردن یک الگوریتم مناسب پرکاربرد است، می‌توان به قضیه زیر اشاره کرد: یک تطابق در یک گراف ماکسمیم است، اگر و فقط اگر گراف دارای هیچ مسیر افزایشی‌ای نباشد.
در واقع با شرط لازم بودن این شرط به ما کمک می‌کند برای پیدا کردن یک تطابق ماکسیمم از یک تطابق M که در ابتدا خالی است شروع کرده و با پیدا کردن مسیرهای افزایشی تطابقمان را بزرگ کنیم. به این ترتیب که یک مسیر افزایشی پیدا کرده و یال‌هایی از آن را که در M هستند از M خارج کنیم و یال‌هایی از آن را که در M نیستند به آن اضافه کنیم. به این ترتیب با وجود این‌که شرط تطابق بودن M از بین نرفته یکی به تعداد یال‌های M اضافه شده است. می توان این کار را آن‌قدر انجام داد تا هیچ مسیر افزایشی دیگری پیدا نشود که در این صورت طبق قضیه 1 می‌توان نتیجه گرفت که M ماکسیمم است. تنها چیزی که باقی می ماند پیدا کردن مسیر افزایشی در یک گراف G می باشد که ما در اینجا الگوریتمی برای پیدا کردن این مسیرها در گراف دوبخشی می‌دهیم الگوریتم پیدا کردن مسیر افزایشی در گراف دوبخشی:

• ورودی: یک گراف دوبخشی با افراز X و Y از رأس‌ها و یک تطابق M در G و مجموعه‌ی U از همه رأس‌های آلوده نشده توسط M در X.
• ارزش‌دهی آغازی: S = U و T = Ø.
• تکرار: اگر S دارای هیچ رأس علامت‌داری نباشد، متوقّف شوید چون مسیر افزایشی دیگری در گراف وجود ندارد. در غیر این‌صورت یک x ε S علامت‌دار نشده را انتخاب کنید. برای جستجوی x هر y ε N(x) ( کهN(x) همسایه‌های x در بخش Y می‌باشد) را طوری در نظر بگیرید که xy در M نباشد. اگر y آلوده نباشد، به کار پایان دهید و از y به عقب حرکت کنید تا یک مسیر افزوده را گزارش دهید (مسیری که از x شروع شده و به y رسیده است). در غیر این‌صورت y با یک w ε X به‌وسیله‌ یال‌های M وصل است. در این صورت y را به T اضافه کنید (از x به آن رسیدیم) و w را به S اضافه کنید (از y به آن رسیدیم). پس از جستجوی همه‌ی چنین‌ یال‌های متصل به x، x را علامت‌دار کرده و تکرار نمایید.

در واقع در این الگوریتم S مجموعه رئوسی در X بودند که از x به آن‌ها رسیدیم و T مجموعه رئوسی در Y بودند که از x به آن‌ها رسیدیم. در واقع پیاده سازی این الگوریتم بوسیله الگوریتم DFS به سادگی قابل انجام است با ادامه دادن این الگوریتم بعد از پیدا کردن هر مسیر افزایشی تا وقتی که دیگر هیچ مسیر افزایشی دیگری در گراف باقی نماند می توان یک تطابق ماکسیمم را در G پیدا کرد. این الگوریتم در واقع از مرتبه‌ی O(ne)می باشد. الگوریتم‌های بهتری نیز برای پیدا کردن تطابق دوبخشی ماکسیمم وجود دارد. مثلاً یون و تارجان الگوریتمی دادند که این مسئله را در O(√ne)حل می کند الگوریتم پیدا کردن تطابق ماکسیمم در حل بسیاری از مسائل می تواند تأثیرگذار باشد. مثلاً می‌توان بزرگترین مجموعه‌ی مستقل (مجموعه‌ی از رئوس که هیچ دوتایی به یکدیگر یال ندارند) در گراف دوبخشی را نیز پیدا کرد یا کوچکترین پوشش رأسی (مجموعه ی از راس ها که به ازای هر یال یک سر آن در این مجموعه باشد)؛ (حل این مسائل به خواننده توصیه می شود). پیدا کردن راه حلی برای این مسائل باعث حل مسائل زیاد دیگری در نظریه گراف شد که تأثیر بسزایی در حل مسائل الگوریتمی دارد. پس داشتن یک برنامه مناسب و دقیق برای پیدا کردن تطابق می تواند بسیار مفید باشد. برای مطالعه بیشتر در این زمینه می توانید به فصل سوم کتاب آشنایی با نظریه گراف نوشته وست مراجعه کنید.