قضیه هال
قضیه هال یا قضیه ازدواج (۱۹۳۵) قضیهای مربوط به شاخه ترکیبیات در ریاضی است. این قضیه که به ریاضیدان انگلیسی، فیلیپ هال نسبت داده میشود، شرط لازم و کافی برای وجود تطابق کامل در گرافهای دوبخشی را بیان میکند. گرافهای دوبخشی به گرافهایی گفته میشوند که رأسها به دو دسته مجزا قابل افراز هستند بگونهای که تمامی یالهای گراف بین گرههای بین دو دسته مختلف باشند.
بر اساس قضیه هال «اگر G یک گراف دوبخشی با افراز مضاعف X و Y باشد، آنگاه G دارای یک جورسازی از X در Y است اگر و فقط اگر به ازای هر زیرمجموعه S از X، تعداد همسایههای S از تعداد اعضای S ناکمتر باشد.»
تعاریف[ویرایش]
۱-مسیر M-متناوب: مسیری است که یالهای آن یکی در میان در تطابق M باشد.
۲-مسیر M-افزوده: مسیر M-متناوبی است که یالهای ابتدایی و انتهایی آن داخل تطابق M نباشد.
در تطابق بیشینه مسیر M-افزوده وجود ندارد زیرا اگر فرض کنیم که یک مسیر M-افزوده در تطابق بیشینه ما وجود داشته باشد میتوان با حذف یالهایی از مسیر افزوده که در تطابق هستند از تطابق و اضافه کردن یالهایی که در تطابق نیستند به تطابق اندازه تطابق را یک یال افزایش داد که این متناقض با بیشینه بودن تطابق است.
اثبات قضیه هال[ویرایش]
لزوم شرط : اگر برای یک مجموعه S شرط فوق برقرار نباشد چون تعداد همسایهها کمتر است پس راسی وجود دارد که برای تطبیق راسی ندارد.
کفایت شرط : داریم به ازای هر زیرمجموعه S از X، تعداد همسایههای S از تعداد اعضای S ناکمتر است. اگرM مجموعه X را اشباع نکند یک مجموعه S را پیدا میکنیم که شرط را نقض کند. فرض کنید u یک راس اشباع نشده در تطابق M باشد. S و T به ترتیب مجموعه راسهایی در X و Y است که از u میتوان با مسیرهای M-متناوب به آنها رسید. ادعا میکنیم که M، مجموعه T را با S-u جور میکند. مسیرهای M-متناوب از u بوسیله یالهایی که در تطابق وجود ندارد به Y و بوسیله یالهایی که در M باشد به X میرسد. چون هیچ مسیر M-افزوده وجود ندارد، هر راس از T در M وجود دارد. علاوه بر این، هر راس از S به جز u از راه یالی در M از راسی در T در دسترس است. از این رو این یالهای M یک نگاشت دوسویی میان T و S-u برقرار میکند و داریم : 
تطابق میان T و S-u مستلزم آن است که T زیر مجموعه همسایههای S باشد. در واقع، T برابر مجموعه همسایههای S است. یک یال میان S و یک راس y عضو Y-T میتوانست یالی باشد که در M نباشد؛ این میتوانست یک مسیر M-متناوب با y بسازد، که با اینکه y در T نباشد در تناقض است. با در نظر گرفتن اینکه T برابر مجموعه همسایههای S است درمیابیم که تعداد همسایههای S که همان T است برابر 
است که کمتر از S است. بنابر این هجموعه S با فرض قضیه در تناقض است.
منابع[ویرایش]
- کتاب آشنایی با نظریه گراف اثر دوگلاس بی.وست
- http://en.wikipedia.org/wiki/Marriage_theorem
