مسیله مجموعه مستقل ماکزیمم و روش های حل آن

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

کلیدواژه ها:

بهینه سازی ، نظریه گراف ، مجموعه مستقل ماکزیمم