شماره رکورد
307
عنوان
پريسا مزروعي: مجموعه مستقل بيشينه گراف ها 10/4/1389
نام نرم افزارها
پريسا مزروعي: مجموعه مستقل بيشينه گراف ها 10/4/1389
نام سازمان
سمينارهاي هفتگي خانه رياضيات اصفهان
وضعيت نشر
خانه رياضيات اصفهان
آدرس وب سايت
www.mathhouse.com
موضوع
گراف , graph
چکيده
نظريه گراف ها شاخه اي از تركيبيات است كه در مدل كردن بسياري از مسائل پيچيده توانا بوده و به صورت گسترده اي مورد استفاده قرار مي گيرد . از جمله اين مسائل مي توان به پيدا كردن بزرگترين مجموعه مستقل خطي در يك گراف اشاره كرد كه كاربرد هاي فراواني در تئوري اطلاعات و بيولوژي مولكولي (molecular biology ) دارد. اين مسئله و مسائل معادل با آن از دسته مسائل NP-hard هستند و تا كنون هيچ الگوريتم محاسبه پذيري ﴿ در زمان قابل قبول ﴾ براي آنها يافت نشده است . در اين سمينار قصد داريم به بررسي رقيق تر اين مسئله بپردازيم . سپس رويكرد هاي مختلف حل اين مسئله را بررسي و راه حل محاسبه پذيري براي اين مسئله در كلاس خاصي از گراف ها ارائه كنيم.
شماره راهنما
ل446