مسئله مجموعه مستقل ماكزيمم و روش هاي حل آن

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