آشنایی با تطابق

تطابق مجموعه‌ای از یال‌هاست که هیچ‌دوتایی از آنها باهم راس مشترک ندارند.

به زبان ریاضی، اگر گراف را $G$ و مجموعه یال‌های آن را $E$ درنظر بگیریم، به زیرمجموعه‌ای از $E$ که هیچ‌یک از دو عضو آن راس مشترکی در $G$ ندارند، تطابق یا مجموعه‌ ناوابسته‌ یال‌ها می‌گویند و آن را با $M$ نشان می‌دهند.

به راسی که در یکی از دو انتهای یال‌های تطابق گراف $G$ واقع شده باشد، راس اشباع (منطبق شده) و در غیر این صورت راس غیراشباع (منطبق نشده) می‌گویند.

تطابق ماکسیمال یک تطابق در $G$ است، به صورتی که هر یال دیگری که در تطابق نیامده باشد را که به آن اضافه کنیم، گراف به وجود آمده خاصیت تطابق بودن خود را از دست بدهد. به عبارتی دیگر، تطابق $M$ زمانی ماکسیمال است که هر یال $G$ حداقل با یکی از یال‌های آن تقاطع داشته باشد.

تطابق ماکسیمم تطابقی است که بیشترین تعداد یال‌های $G$ را دارد. بنابراین می‌توان نتیجه گرفت هر تطابق ماکسیمم، یک تطابق ماکسیمال است، ولی هر تطابق ماکسیمال لزوما یک تطابق ماکسیمم نیست.

تطابق کامل نیز تطابقی است که در آن همه راس‌ها اشباع هستند (در اصل تعداد یال‌های آن برابر $|G| / 2$ است). همچنین به راحتی می‌توان دید که تطابق ماکسیمال حداقل برابر نصف تطابق ماکسیمم است.

مسیر متناوب، مسیری است که یال‌های آن یکی در میان در میان یال‌های تطابق و خارج از یال‌های تطابق است.

مسیر افزایشی، مسیری متناوب است که یال‌های اول و آخر آن خارج از یال‌های تطابق هستند.

یک تطابق ماکسیمم است، اگر و تنها اگر مسیر افزایشی نداشته باشد که این نتیجه‌گیری به قضیه‌ی برژ نیز معروف است. اثبات این قضیه نیز به روش برهان خلف قابل انجام است:

فرض کنید تطابق $M'$ تطابقی ماکسیمال بدون مسیر افزایشی و تطابق $M$ تطابق بیشینه است. در این صورت گراف $M \Delta M'$ را درنظر بگیرید. درجه هر راس در آن حداکثر برابر دو است. پس این گراف از تعدادی دور و مسیر یکی‌درمیان تشکیل می‌شود. در دور‌ها و مسیرهای زوج، تعداد یال‌های هر دو تطابق باهم برابر است. در مسیرهای فرد نیز حتما اولین و آخرین یال از $M$ است، زیرا در غیر این صورت می‌توانستیم به جای یال‌های $M$ در مسیر از یال‌های $M'$ استفاده کنیم و اندازه تطابق را افزایش دهیم. پس اگر مسیر فردی داشته باشیم یعنی حداقل یک مسیر افزایشی داریم که این تناقض است. پس نتیجه میگیریم که مسیر فردی نداریم و $|M| = |M'|$.

به مجموعه‌ای (پوششی) از رئوس که هر یال حداقل یکی از دو سرش در این مجموعه آمده باشد، پوشش راسی می‌گوییم.

به مجموعه‌ای (پوششی) از یال‌ها که هر راس حداقل یکی از یال‌های مجاورش در این مجموعه آمده باشد، پوشش یالی می‌گوییم.

به پوشش راسی با مینیمم تعداد راس، مینیمم پوشش راسی و به پوشش یالی با مینیمم تعداد یال، مینیمم پوشش یالی می‌گوییم.