PDA

View Full Version : سوال: یافتن بزرگترین انطباق درگراف ها



fatemegm
جمعه 04 تیر 1389, 15:45 عصر
انطباق: زیرمجموعه ای از لبه ها که هیچ دو لبه ای به یک راس وارد نشده اند
انطباق کامل: انطباقی که در آن به هر راس یک لبه وارد شده
پروژه ما یافتن بزرگترین انطباق در گرافه که همون انطباق کامل می شه
میشه یه ایده به من بدید هیچ ایده ای ندارم!!

qwerty11
شنبه 05 تیر 1389, 15:35 عصر
چرا اینجا این موضوع رو مطرح کردین !؟ :-/
جاش تو تاپیک الگوریتمه ! ممنون میشم اگر جناب مدیر زحمتشو بکشه ...

اولاً : احتمالاً باید پروژتون یافتن بزرگترین انطباق (matching) تو گراف 2 بخشی باشه چون تو این نوع گراف ها الگوریتم هایی واسه حل این سوال وجود داره.

پس با فرض اینکه گرافتون 2 بخشیه :
http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipar tite_graphs