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

في نظرية الرسم البياني ،  نعرف مجموعة مستقلة  أومجموعة مستقرة ( stable set  أو independent set  ) بأنها  مجموعة من رؤوس  رسم بياني والتي كل رأسين بها هما غير متجاوران. بمعنى آخر ،المجموعة المستقلة هي مجموعة S من الرؤوس بحيث لا يوجد ضلع يربط بين كل رأسين في S.  وهذا يعني أن  كل ضلع في الرسم البياني له رأس واحد عالأكثر  واحدة على الأكثر في S. حجم المجموعة المستقلة هو عدد الرؤوس بها . تسمى المجموعات المستقلة أيضا بمجموعات مستقرة داخليا.
المجموعة المستقلة القصوى  ( maximal independent set ) هي إما مجموعة مستقلة بحيث أن إضافة أي رأس لها ينتج عنه ضلع ينتمي بالكامل لهذه المجموعة  أو مجموعة من جميع رؤوس الرسم البياني الخالي (أي لايحتوي على أضلاع).
تعرف المجموعة المستقلة القصوى بشكل آخر بأنها مجموعة مستقلة والتي لها أكبر حجم ممكن للرسم البياني G المحدد. يُسمى هذا الرقم بعدد الاستقلال ( independence ) لـ G ، ويرمز بالرمز . تعتبر مسألة  إيجاد المجموعة المستقلة القصوى مشكلة من النوع  NP-hard  بمسائل الأمثلية. فبالتالي فإنه من غير المحتمل وجود خوارزمية فعالة لإيجاد الحد الأقصى المستقل لمجموعة من الرسم البياني.
كل  مجموعة مستقلة قصوى هي  أيضًا الحد الأقصى ، لكن العكس ليس دائما صحيح.

العلاقة مع غيرها من متغيرات الرسم البياني

نقول أن المجموعة مستقلة إذا وفقط إذا كانت تجمع (Clique) في تكملة الرسم البياني ، وبالتالي فإن المفهومين متكاملان. في الواقع ، تحتوي الرسوم البيانية الكبيرة  التي ليس لها عصابات كبيرة على مجموعات كبيرة مستقلة ، والذي يتم دراسته   في نظرية رامزي (Ramsey theory).
أيضا يقال أن المجموعة مستقلة إذا وفقط إذا كان المكمل لها يمثل  غطاء الرأس . لذلك فإن مجموع حجم أكبر مجموعة مستقلة  وحجم الحد الأدنى من غطاء الرأس  يساوي عدد الرؤوس في الرسم البياني ، أي أن .
تعتبر مسألة تلوين رؤوس الرسم البياني G تجزئة (partition) لمجموعة رؤوس G إلى مجموعات جزئية مستقلة. ومن هنا يكون الحد الأدنى لعدد الألوان المطلوبة في تلوين الرؤوس ، المعروف بالعدد اللوني ،هو  على الأقل حاصل قسمة عدد الرؤوس في  والرقم المستقل .
في الـرسم ثنائي الأطراف أو التجزئة الذي لايحتوي على أي رؤوس معزولة ، فإن عدد الاستقلال يساوي عدد الأضلاع في الحد الأدنى لـغطاء الأضلاع ؛ هذه هي نظرية كونيج .

مجموعة مستقلة قصوى

تسمى المجموعة المستقلة  التي ليس لها مجموعات جزئية بمجموعة مستقلة أخرى بأنها مجموعة قصوى . هذه المجموعات هي مجموعات مسيطرة . يحتوي كل رسم بياني على  من  على الأكثر من المجموعات المستقلة القصوى   لكن العديد من الرسوم البيانية تحتوي على أقل من ذلك العدد بكثير. يتم الحصول على عدد المجموعات المستقلة القصوى في الرسوم البيانية لدورة به  من الرؤوس  بواسطة أرقام Perrin ، ويتم إستنتاج عدد المجموعات المستقلة القصوى في الرسوم البيانية لمسار به  من الرؤوس بواسطة تسلسل Padovan . لذلك ، يتناسب كلا الرقمين مع قوى الرقم البلاستيكي 1.324718 .

مجموعات مستقلة قصوى وأكبر تجمعات

تعتبر مسألتي  المجموعة المستقلة و التجميع متكاملتين: فأي تجميع في G هو مجموعة مستقلة في الرسم البياني التكميلي لـ G والعكس صحيح. لذلك  قد يتم تطبيق العديد من النتائج الحسابية بشكل جيد على حد سواء لهاتين المسألتين. على سبيل المثال ، تحتوي النتائج المرتبطة بمسألة التجميع على النتائج  التالية:
مسائل قرار مجموعة مستقلة هي NP- كاملة ، وبالتالي لا يعتقد أن هناك خوارزمية فعالة لحلها. مسائل المجموعة المستقلة القصوى هي من النوع NP-hard فمن الصعب أيضًا تقريبها .

الخوارزميات الدقيقة

مسألة إيجاد مجموعة مستقلة قصوى هي  NP-hard. ومع ذلك ، يمكن حلها بشكل أكثر كفاءة بزمن   بإستخدام خوارزمية القوة الغاشمة التي تدرس كل مجموعة جزئية من الرؤوس والتحقق ما إذا كانت  مجموعة مستقلة ام لا.
في عام 2017 ، تمكن حلها بزمن    باستخدام مساحة متعددة الحدود  . عند الإقتصار على الرسوم البيانية والذي به أقصى درجة هي  3 ، فيمكن حلها بزمن قدره   .
بالنسبة للعديد من فئات الرسوم البيانية ، يمكن العثور على مجموعة مستقلة للوزن الأقصى بزمن متعدد الحدود. مثال على ذلك الرسوم البيانية الخالية من المخلب و  الرسوم البيانية خالية من   والرسوم البيانية المثالية . بالنسبة للرسوم البيانية الوتريه  فيمكن الحصول على مجموعة مستقلة موزونه قصوى بزمن خطي.
التحلل المعياري هو أداة جيدة لحل مسألة ايجاد مجموعة مستقلة موزونه قصوى ؛ خوارزمية الوقت الخطي على الرسوم البيانية هي المثال الأساسي لذلك. أداة أخرى مهمة هي فواصل التجمع (Clique separator) كما وصفها تارجان.
في الرسم البياني ثنائي الأطراف ، يمكن تضمين جميع الرؤوس غير الموجودة في الحد الأدنى من غطاء الرأس في  مجموعة مستقلة قصوى ويمكن قراءة  نظرية Kőnig  لتفاصيل أكثر . فبالتالي يمكن الحصول على الحد الأدنى من أغطية الرأس باستخدام خوارزمية مطابقة ثنائية الطرف.

خوارزميات التقريب

بشكل عام ، لا يمكن تقريب مسألة إيجاد مجموعة مستقلة قصوى  إلى عدد ثابت في كثيرة حدود (ما لم تكن P = NP). في الواقع ، فإن أقصى مجموعة مستقلة  بشكل عام عبارة عن Poly-APX-Complete ، مما يعني أنه صعب مثل أي مشكلة يمكن تقريبها إلى عامل متعدد الحدود. بالرغم من ذلك، هناك خوارزميات تقريب فعالة لفئات محدودة من الرسوم البيانية.

إيجاد  أكبر المجموعات مستقلة

يمكن حل مسألة  إيجاد مجموعة مستقلة قصوى بزمن متعدد الحدود   بإستخدام خوارزمية جشعة (greedy ) تافهة. يمكن العثور على جميع المجموعات المستقلة القصوى في زمن قدره .