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

تكون المجموعة مستقلة إذا وفقط إذا كانت زمرة في متمم الرسم البياني ، لذا فإن المفهومين متكاملان. في الواقع، تحتوي الرسوم البيانية الكبيرة بما يكفي والتي لا تحتوي على زمر كبيرة على مجموعات مستقلة كبيرة، وهو موضوع يتم استكشافه في نظرية رامزي .

تكون المجموعة مستقلة إذا وفقط إذا كانت مكملتها غطاءً للرؤوس . ^{[ 4 ]} لذلك، فإن مجموع حجم أكبر مجموعة مستقلة يساوي${\displaystyle \alpha (G)}$وحجم غطاء الرأس الأدنى${\displaystyle \beta (G)}$يساوي عدد الرؤوس في الرسم البياني.

تلوين رؤوس الرسم البياني${\displaystyle G}$يتوافق ذلك مع تقسيم مجموعة رؤوسها إلى مجموعات فرعية مستقلة. ومن ثم، فإن الحد الأدنى لعدد الألوان اللازمة في تلوين الرؤوس يُسمى العدد اللوني.${\displaystyle \chi (G)}$، على الأقل هو ناتج قسمة عدد الرؤوس في${\displaystyle G}$والعدد المستقل${\displaystyle \alpha (G)}$.

في الرسم البياني ثنائي الأجزاء بدون رؤوس معزولة، فإن عدد الرؤوس في مجموعة مستقلة قصوى يساوي عدد الحواف في تغطية حواف دنيا ؛ هذه هي نظرية كونيغ .

تُسمى المجموعة المستقلة التي لا تُمثل مجموعة جزئية فعلية من مجموعة مستقلة أخرى مجموعةً عظمى . وتُعرف هذه المجموعات بالمجموعات المهيمنة . يحتوي كل رسم بياني على 3n/3 مجموعة عظمى مستقلة على الأكثر ^{، [} 5 ^{] ولكن العديد} من الرسوم البيانية تحتوي على عدد أقل بكثير. يُعطى عدد المجموعات العظمى المستقلة في الرسوم البيانية الدورية ذات n رأسًا بأعداد بيرين ، ويُعطى عدد المجموعات العظمى المستقلة في الرسوم البيانية المسارية ذات n رأسًا بمتتالية بادوفان . ^{[ 6 ]} لذلك، يتناسب كلا العددين مع قوى العدد 1.324718...، وهي النسبة البلاستيكية .

تُعدّ مسألة المجموعات المستقلة ومسألة الزمر مُكمّلتين لبعضهما: فالزمرة في الرسم البياني G هي مجموعة مستقلة في الرسم البياني المُكمّل لـ G ، والعكس صحيح. لذا، يُمكن تطبيق العديد من النتائج الحسابية على كلتا المسألتين بكفاءة متساوية. على سبيل المثال، تُفضي النتائج المُتعلقة بمسألة الزمر إلى النتائج التالية:

• تُعد مشكلة اتخاذ القرار بشأن المجموعة المستقلة مشكلة NP-كاملة ، وبالتالي لا يُعتقد أن هناك خوارزمية فعالة لحلها.
• مشكلة المجموعة المستقلة القصوى هي مشكلة صعبة من نوع NP، ومن الصعب أيضًا تقريبها .

على الرغم من العلاقة الوثيقة بين الزمر القصوى والمجموعات المستقلة القصوى في الرسوم البيانية العشوائية، إلا أن مشكلتي المجموعة المستقلة والزمرة قد تختلفان اختلافًا كبيرًا عند حصرهما في فئات خاصة من الرسوم البيانية. على سبيل المثال، بالنسبة للرسوم البيانية المتفرقة (الرسوم البيانية التي يكون فيها عدد الحواف على الأكثر ثابتًا مضروبًا في عدد الرؤوس في أي رسم بياني فرعي)، فإن الزمرة القصوى لها حجم محدود ويمكن إيجادها بدقة في وقت خطي؛ ^{[ 7 ]} ومع ذلك، بالنسبة لنفس فئات الرسوم البيانية، أو حتى بالنسبة للفئة الأكثر تقييدًا من الرسوم البيانية ذات الدرجة المحدودة، فإن إيجاد المجموعة المستقلة القصوى هو مسألة MAXSNP-كاملة ، مما يعني أنه بالنسبة لثابت ما c (يعتمد على الدرجة)، فإن إيجاد حل تقريبي يقع ضمن عامل c من الحل الأمثل هو مسألة NP-صعبة . ^{[ 8 ]}

تُعدّ مسألة إيجاد أكبر مجموعة مستقلة مسألة صعبة من نوع NP. ومع ذلك، يمكن حلّها بكفاءة أكبر من زمن O( n² ^-  2n ⁾ الذي تستغرقه خوارزمية البحث الشامل البسيطة التي تفحص كل مجموعة فرعية من الرؤوس وتتحقق مما إذا كانت مجموعة مستقلة.

اعتبارًا من عام 2017، يمكن حل هذه المسألة في زمن قدره O(1.1996 ⁿ ) باستخدام فضاء متعدد الحدود. ^{[ 9 ]} وعند تقييدها بالرسوم البيانية ذات الدرجة القصوى 3، يمكن حلها في زمن قدره O(1.0836 ⁿ ). ^{[ 10 ]}

بالنسبة للعديد من فئات الرسوم البيانية، يمكن إيجاد مجموعة مستقلة ذات وزن أقصى في وقت متعدد الحدود. ومن الأمثلة الشهيرة على ذلك الرسوم البيانية الخالية من المخالب ^{[ 11 ]} ، والرسوم البيانية الخالية من _P5 [ ^{12 ] ،} والرسوم البيانية المثالية ^{[ 13 ]} . أما بالنسبة للرسوم البيانية الوترية ، فيمكن إيجاد مجموعة مستقلة ذات وزن أقصى في وقت خطي ^{[ 14 ] .}

يُعدّ التفكيك المعياري أداةً فعّالةً لحلّ مسألة المجموعة المستقلة ذات الوزن الأقصى؛ وتُعتبر خوارزمية الزمن الخطي على الرسوم البيانية التكميلية مثالًا أساسيًا على ذلك. ومن الأدوات المهمة الأخرى فواصل الزمر كما وصفها تارجان. ^{[ 15 ]}

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

بشكل عام، لا يمكن تقريب مسألة المجموعة المستقلة القصوى إلى عامل ثابت في وقت متعدد الحدود (إلا إذا كانت P = NP). في الواقع، تُعدّ مسألة المجموعة المستقلة القصوى عمومًا مسألةً كاملةً من نوع Poly-APX ، أي أنها صعبة كأي مسألة يمكن تقريبها إلى عامل متعدد الحدود. ^{[ 16 ]} ومع ذلك، توجد خوارزميات تقريب فعّالة لفئات محدودة من الرسوم البيانية.

يمكن حل مشكلة إيجاد مجموعة مستقلة قصوى في وقت متعدد الحدود باستخدام خوارزمية جشعة متوازية بسيطة . ^{[ 22 ]} يمكن إيجاد جميع المجموعات المستقلة القصوى في وقت O(3 ^{n /3} ) = O(1.4423 ⁿ ).

تُطرح مسألة العد #IS، التي تُعطى على رسم بياني غير موجه، سؤالًا حول عدد المجموعات المستقلة التي يحتويها. هذه المسألة غير قابلة للحل، أي أنها مسألة كاملة من فئة ♯P ، حتى على الرسوم البيانية ذات الدرجة القصوى ثلاثة. ^{[ 23 ]} ومن المعروف أيضًا أنه، بافتراض أن NP تختلف عن RP ، لا يمكن تقريب المسألة بشكل عملي بمعنى أنها لا تملك مخطط تقريب متعدد الحدود بالكامل مع العشوائية (FPRAS)، حتى على الرسوم البيانية ذات الدرجة القصوى ستة؛ ^{[ 24 ]} ومع ذلك، فإنها تملك مخطط تقريب متعدد الحدود بالكامل (FPTAS) في حالة كون الدرجة القصوى خمسة. ^{[ 25 ]} المسألة #BIS، المتعلقة بعد المجموعات المستقلة على الرسوم البيانية ثنائية الأجزاء ، هي أيضًا مسألة كاملة من فئة ♯P ، حتى على الرسوم البيانية ذات الدرجة القصوى ثلاثة. ^{[ 26 ]} من غير المعروف ما إذا كانت #BIS تقبل مخطط تقريب متعدد الحدود بالكامل (FPRAS). ^{[ 27 ]}

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