307

پريسا مزروعي: مجموعه مستقل بيشينه گراف ها 10/4/1389

خانه رياضيات اصفهان

www.mathhouse.com

نظريه گراف ها شاخه اي از تركيبيات است كه در مدل كردن بسياري از مسائل پيچيده توانا بوده و به صورت گسترده اي مورد استفاده قرار مي گيرد . از جمله اين مسائل مي توان به پيدا كردن بزرگترين مجموعه مستقل خطي در يك گراف اشاره كرد كه كاربرد هاي فراواني در تئوري اطلاعات و بيولوژي مولكولي (molecular biology ) دارد. اين مسئله و مسائل معادل با آن از دسته مسائل NP-hard هستند و تا كنون هيچ الگوريتم محاسبه پذيري ﴿ در زمان قابل قبول ﴾ براي آنها يافت نشده است . در اين سمينار قصد داريم به بررسي رقيق تر اين مسئله بپردازيم . سپس رويكرد هاي مختلف حل اين مسئله را بررسي و راه حل محاسبه پذيري براي اين مسئله در كلاس خاصي از گراف ها ارائه كنيم.

ل446