سلام
من اصلا یحث تطابق ها رو توی گراف نمی فهمم
میشه برام توضیح بدید
کلا چقدر گراف سخته! سوالای علوم کامپیوتر هم ازون سخت تر!! من که بیخیال تستاش در گراف شدم
(۱۱ آذر ۱۳۹۲ ۱۱:۳۵ ب.ظ)lotus نوشته شده توسط: سلاممن هم با این مبحث پارسال خیلی مشکل داشتم ولی امسال که باز خوندم (همین نیم ساعت پیش )فهمیدم چقدر ساده بوده
من اصلا یحث تطابق ها رو توی گراف نمی فهمم
میشه برام توضیح بدید
کلا چقدر گراف سخته! سوالای علوم کامپیوتر هم ازون سخت تر!! من که بیخیال تستاش در گراف شدم
ببینید شما هر وقت خواستید تشخیص بدید که یک گرف تطابق کامل داره یا نه باید اینکارو انجام بدین
یه گراف دوبخشی رو در نظر بگیرید مثل این شکل
راسهای سمت چپ xها هستند و سمت چپی ها y
اول یه زیر مجموعه دلخواه از xها رو در نظر بگیرید مثلا من این مجموعه رو در نظر میگیرم {[tex]x_{1},x_{2}[/tex]}
واسمش رو میذاریم مثلا مجموعه A
بعد ببینیم این x ها به چه yهایی وصل هستن که میشه [tex]y_{1},y_{2}[/tex]
اسم این مجموعه رو میذاریم R
حالا اگه اندازه مجموعه A بیشتر ازRباشه تطابق وجود نداره برای اینکه وجود داشته باشه باید به ازای هر مجموعه از xها، [tex]A\leq R[/tex]
واسه مثال بالا اندازه هر دو مجموعه ۲ هست یعنی اندازه شون با هم برابره پس باید یه مجموعه دیگه رو در نظر بگیریم
مثلا اگه این زیرمجموعه از xها رو در نظر بگیریم{[tex]x_{1},x_{2},x_{3}[/tex]}
مجموعه yهامون اینه {[tex]y_{1},y_{3}[/tex]}
چون تعداد yهامون از xها کمتر شده پس شکل ما تطابق کامل ندارد.
به طور کلی باید به دنبال زیر مجموعه ای از xها بگردیم که تعداد yهاشون از xها کمتره اگه پیدا شد تطابق نقض شده ولی اگه پیدا نکردیم
تطابق وجود داره
امیدوارم مطلب رو رسونده باشم
(۱۲ آذر ۱۳۹۲ ۰۶:۲۰ ب.ظ)maryam.raz نوشته شده توسط:(11 آذر ۱۳۹۲ ۱۱:۳۵ ب.ظ)lotus نوشته شده توسط: سلاممن هم با این مبحث پارسال خیلی مشکل داشتم ولی امسال که باز خوندم (همین نیم ساعت پیش )فهمیدم چقدر ساده بوده
من اصلا یحث تطابق ها رو توی گراف نمی فهمم
میشه برام توضیح بدید
کلا چقدر گراف سخته! سوالای علوم کامپیوتر هم ازون سخت تر!! من که بیخیال تستاش در گراف شدم
ببینید شما هر وقت خواستید تشخیص بدید که یک گرف تطابق کامل داره یا نه باید اینکارو انجام بدین
یه گراف دوبخشی رو در نظر بگیرید مثل این شکل
راسهای سمت چپ xها هستند و سمت چپی ها y
اول یه زیر مجموعه دلخواه از xها رو در نظر بگیرید مثلا من این مجموعه رو در نظر میگیرم {[tex]x_{1},x_{2}[/tex]}
واسمش رو میذاریم مثلا مجموعه A
بعد ببینیم این x ها به چه yهایی وصل هستن که میشه [tex]y_{1},y_{2}[/tex]
اسم این مجموعه رو میذاریم R
حالا اگه اندازه مجموعه A بیشتر ازRباشه تطابق وجود نداره برای اینکه وجود داشته باشه باید به ازای هر مجموعه از xها، [tex]A\leq R[/tex]
واسه مثال بالا اندازه هر دو مجموعه ۲ هست یعنی اندازه شون با هم برابره پس باید یه مجموعه دیگه رو در نظر بگیریم
مثلا اگه این زیرمجموعه از xها رو در نظر بگیریم{[tex]x_{1},x_{2},x_{3}[/tex]}
مجموعه yهامون اینه {[tex]y_{1},y_{3}[/tex]}
چون تعداد yهامون از xها کمتر شده پس شکل ما تطابق کامل ندارد.
به طور کلی باید به دنبال زیر مجموعه ای از xها بگردیم که تعداد yهاشون از xها کمتره اگه پیدا شد تطابق نقض شده ولی اگه پیدا نکردیم
تطابق وجود داره
امیدوارم مطلب رو رسونده باشم
بلی ی ی ی
بسیار خوب فهمیدم! ممنونم