قضیه هال-تطبیق کامل

[قله بلند]

سلام دوستان
قضیه ای هست به نام قضیه هال که در مورد تطبیق کامل بحث می کنه. یه مبحث دیگه هم هست به نام تطبیق ماکزیمم. هر دو در الگوریتم پیشرفته وجود دارند.
در قضیه هال، بحث همسایگی رو مطرح می کنه. از ویکی پدیا صفحه مربوط رو دانلود کردم ولی متوجه اصل مطلب نمی شم .
می شه لطف کنید و راهنمایی کنید

[qwerty11]

قضیه ی هال در مورد امکان وجود داشتن تطابق کامل بحث میکنه:

فرض کن یه گراف 2 بخشی G = (X, Y, E) Iداریم. اگر هر زیرمجموعه ی k عضوی از X به حداقل k عضو از Y وصل باشه در این صورت تطابق کاملی در G وجود خواهد داشت. این رابطه یه رابطه ی 2 طرفست.

تطابق ماکسیمم : یک تطابق که بیشترین تعداد یال های ممکن را داشته باشد.

[قله بلند]

سلام
ضمن تشکر از توجه شما



تطابق ماکسیمم : یک تطابق که بیشترین تعداد یال های ممکن را داشته باشد.

این بیشترین تعداد یال ممکن چه طوری به دست می آید؟ یعنی چه طوری فرض می شه؟
در تطابق کامل، تعداد راس های در دو مجموعه S و T باید با هم مساوی باشند تا تطبیق کامل به دست بیاد. درسته؟
ولی در تطبیق ماکزیمم می تونن با هم مساوی باشند ولی شرط اینکه تعداد تطابق های زیر مجموعه ای از S باید از بیشتر یا مساوی باشد رو نداره. درسته؟

[qwerty11]

این بیشترین تعداد یال ممکن چه طوری به دست می آید؟ یعنی چه طوری فرض می شه؟ خوب الگوریتم های مختلفی برای به دست آوردن بیشترین تعداد وجود داره.
http://en.wikipedia.org/wiki/Maximum_matching#Maximum_matchings_in_bipartite_gr aphs


در تطابق کامل، تعداد راس های در دو مجموعه S و T باید با هم مساوی باشند تا تطبیق کامل به دست بیاد. درسته؟ بله


ولی در تطبیق ماکزیمم می تونن با هم مساوی باشند ولی شرط اینکه تعداد تطابق های زیر مجموعه ای از S باید از بیشتر یا مساوی باشد رو نداره. درسته؟ بله. در تطابق ماکسیمم لزوماً ممکنه همه ی رئوس در تطابق وجود نداشته باشند.