كل ما تريد معرفته عن مجموعة مستقلة (نظرية الرسومات)

في نظرية الرسم البياني، نعرف مجموعة مستقلة أومجموعة مستقرة (stable set أو independent set) بأنها مجموعة من رؤوس رسم بياني والتي كل رأسين بها هما غير متجاوران. بمعنى آخر، المجموعة المستقلة هي مجموعة S من الرؤوس بحيث لا يوجد ضلع يربط بين كل رأسين في S. وهذا يعني أن كل ضلع في الرسم البياني له رأس واحد عالأكثر واحدة على الأكثر في S. حجم المجموعة المستقلة هو عدد الرؤوس بها. تسمى المجموعات المستقلة أيضا بمجموعات مستقرة داخليا.

المجموعة المستقلة القصوى (maximal independent set ) هي إما مجموعة مستقلة بحيث أن إضافة أي رأس لها ينتج عنه ضلع ينتمي بالكامل لهذه المجموعة أو مجموعة من جميع رؤوس الرسم البياني الخالي (أي لايحتوي على أضلاع).

تعرف المجموعة المستقلة القصوى بشكل آخر بأنها مجموعة مستقلة والتي لها أكبر حجم ممكن للرسم البياني G المحدد. يُسمى هذا الرقم بعدد الاستقلال (independence) لـ G ، ويرمز بالرمز







α

(

G

)





{\displaystyle \alpha (G)}



. تعتبر مسألة إيجاد المجموعة المستقلة القصوى مشكلة من النوع NP-hard بمسائل الأمثلية. فبالتالي فإنه من غير المحتمل وجود خوارزمية فعالة لإيجاد الحد الأقصى المستقل لمجموعة من الرسم البياني.

كل مجموعة مستقلة قصوى هي أيضًا الحد الأقصى، لكن العكس ليس دائما صحيح.