قضایا ی مینماکس¶

\(\alpha + \beta = n\)¶

مکمل یک مجموعه مستقل یک پوشش راسی و مکمل یک پوشش راسی یک مجموعه مستقل است(چرا؟). در نتیجه اگر ماکسیمم مجموعه مستقل را در نظر بگیرید مکمل آن مینیمم پوشش راسی است و بالعکس.

\(\alpha^{\prime} + \beta^{\prime} = n\)¶

ابتدا باید فرض کنیم که گراف راس تنها ندارد زیرا در غیراینصورت پوشش یالی برای این گراف تعریف نمی شود.

حالا مینیمم پوشش یالی را در نظر بگیرید.

در ابتدا می توان نتیجه گرفت در این مجموعه یالی دور وجود ندارد (در اینصورت با حذف یکی از یال های دور به مجموعه کوچک تری رسید که همچنان پوشش یالی است). پس هر مولفه همبندی آن یک درخت است.

سپس می توان نتیجه گرفت در هیچکدام از درخت ها فاصله بیشتر از 2 وجود ندارد (چرا؟). پس هر کدام از درخت ها یک ستاره هستند.

تعداد ستاره ها \(n-\beta^{\prime}\) می باشد. و می توان از هر ستاره دقیقا یک یال را انتخاب کرد و یک تطابق تشکیل داد که اندازه آن کمتر مساوی تطابق ماکسیمم است. یعنی \(n-\beta^{\prime} \leq \alpha^{\prime}\) در نتیجه \(n \leq \alpha^{\prime} + \beta^{\prime}\).

حالا تطابق ماکسیمم را در نظر بگیرید.

هر راسی مثل \(u\) که با تطابق ماکسیمم پوشش داده نمی شود را در نظر بگیرید. تمام مجاور های \(u\) باید با تطابق ماکسیمم پوشش داده شود (چرا؟) و چون راس تنها نداریم \(u\) حداقل یک مجاور دارد.

حالا یک پوشش یالی می سازیم. ابتدا تمام یال های تطابق را به آن اضافه می کنیم. سپس به ازای هر راسی که با تطابق ماکسیمم پوشش داده نشده یکی از یال های مجاورش را به پوشش راسی اضافه می کنیم. حالا پوشش راسی به اندازه \(n - \alpha^{\prime}\) داریم زیرا که \(\alpha^{\prime}\) یال اولیه هر کدام دو راس را پوشش دادند و بقیه یال ها هر کدام یک راس را پوشش دادند. \(n-\alpha^{\prime} \geq \beta^{\prime}\) در نتیجه \(n \geq \alpha^{\prime} + \beta^{\prime}\).

در نهایت دو قسمت بالا حکم را نتیجه می دهند.

\(\beta \geq \alpha^{\prime}\)¶

تطابق ماکسیمم را در نظر بگیرید. تنها برای اینکه یال های مربوط به این تطابق را پوشش دهید به \(\alpha^{\prime}\) راس نیاز دارید. (هر راس حداکثر می تواند یکی از آن ها را پوشش دهد). پس \(\beta \geq \alpha^{\prime}\).

\(\alpha^{\prime} = \beta\)¶

در قسمت بالا داشتیم \(\beta \geq \alpha^{\prime}\) پس هر پوشش راسی بزرگتر مساوی یک تطابق است. پس اگر یک تطابق پیدا کنیم که برابر با یک پوشش راسی باشد در اینصورت حکم را ثابت کردیم همچنین آن تطابق ماکسیمم خواهد بود و آن پوشش راسی مینیمم خواهد بود.

یک پوشش راسی مینیمم را در نظر بگیرید. فرض کنید گراف دو بخشی ما دارای دوبخش \(X,Y\) است و مجموعه راس های پوشش راسی ما \(X1 \cup Y1\) است که \(X1\) از بخش \(X\) و \(Y1\) از بخش \(Y\) می باشد همچنین \(X2=X-X1, Y2=Y-Y1\).

حالا گرافی که تنها شامل راس های \(X1,Y2\) باشند را در نظر بگیرید. می خواهیم یک تطابق کامل از \(X1\) به \(Y2\) پیدا می کنیم (یعنی کل راس های \(X1\) درون تطابق باشند).

برقرار بودن شرط هال را برای پیدا کردن یک تطابق کامل از \(X1\) به \(Y2\) بررسی می کنیم. فرض کنید \(S \subseteq X1\) ادعا می کنیم \(|S| \leq |n(S)|\) برقرار است. فرض کنید برقرار نباشد یعنی \(|S| > |n(S)|\) آنگاه اگر مجموعه \(S\) را از پوشش راسی حذف کنیم و مچموعه \(n(S)\) را به پوشش راسی اضافه کنیم همچنان همه یال ها پوشانده می شوند و به یک پوشش راسی کوچکتر رسیدیم که با مینیمم بودن پوشش راسی فعلی در تناقض است. پس شرط هال برقرار است.

مشابها می توان یک تطابق کامل از \(Y1\) به \(X2\) پیدا کرد. که نتیجه می دهد ما تطابقی پیدا کردیم که اندازه آن برابر با پوشش راسی است.

\(\beta^{\prime} = \alpha\)¶

از بخش های قبل داشتیم‌ که \(\alpha^{\prime} = \beta\) و \(n - \alpha = \beta\) و \(n - \beta^{\prime} = \alpha^{\prime}\) برقرارند.

در نتیجه \(n - \alpha = n - \beta^{\prime}\) پس \(\alpha = \beta^{\prime}\).