كتب get independent groups

في علوم الكمبيوتر ، تمت دراسة العديد من المشكلات الحسابية المتعلقة بمجموعات مستقلة.

• في مسألة المجموعة المستقلة القصوى ، يكون المعطيات هنا عبارة عن رسم بياني غير موجه، والناتج هو مجموعة مستقلة قصوى في الرسم البياني. إذا كان هناك عدة مجموعات مستقلة قصوى، فالمطلوب هنا مجموعة واحدة فقطاجة واحدة فقط. يشار إلى هذه المسألة أحيانًا باسم " vertex packing ".
• في مسألة مجموعة مستقله موزونه قصوى، يكون المتطلب هنا عبارة عن رسم بياني غير موجه مع أوزان لرؤوسه ويكون الناتج مجموعة مستقلة ذات أقصى مجموع للأوزان. تعتبر مسألة المجموعة المستقلة القصوى حالة خاصة من المجموعة المستقلة الموزونه القصوى والتي تكون فيها جميع الأوزان واحدة.
• في مسألة الإدراج المستقل القصوى ، نحتاج لرسم بغير موجه، ويتم البحث هنا عن قائمة بجميع مجموعاته المستقلة القصوى. يمكن حل هذه المسألة باستخدام خوارزمية روتين فرعي لمشكلة قائمة مجموعة الحد الأقصى المستقل، لأنه يجب تضمين مجموعة الحد الأقصى المستقل بين جميع مجموعات الحد الأقصى المستقل.
• مسألة قرار المجموعة المستقلة أيضا تتطلب رسم بياني غير موجه ورقم k ، وتهتم بإيجاد قيمة منطقية والتي تكون صائبة في حالة احتواء الرسم البياني على مجموعة مستقلة من الحجم k ، وخاطئة فيما عدا ذلك.

المسائل الثلاث الاولى المذكوره أعلاه مهمة في التطبيقات العملية. بينما مسألة قرار المجموعة المستقلة ليست كذلك لكنها ضرورية من أجل تطبيق نظرية اكتمال NP على المشكلات المتعلقة بالمجموعات المستقلة.

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

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

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

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

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

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

في عام 2017 ، تمكن حلها بزمن باستخدام مساحة متعددة الحدود. عند الاقتصار على الرسوم البيانية والذي به أقصى درجة هي 3 ، فيمكن حلها بزمن قدره .

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

التحلل المعياري هو أداة جيدة لحل مسألة ايجاد مجموعة مستقلة موزونه قصوى ؛ خوارزمية الوقت الخطي على الرسوم البيانية هي المثال الأساسي لذلك. أداة أخرى مهمة هي فواصل التجمع (Clique separator) كما وصفها تارجان.

في الرسم البياني ثنائي الأطراف ، يمكن تضمين جميع الرؤوس غير الموجودة في الحد الأدنى من غطاء الرأس في مجموعة مستقلة قصوى ويمكن قراءة نظرية Kőnig لتفاصيل أكثر . فبالتالي يمكن الحصول على الحد الأدنى من أغطية الرأس باستخدام خوارزمية مطابقة ثنائية الطرف.

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

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

مجموعات مستقلة في الرسوم البيانية تقاطع الفاصل

مجموعات مستقلة في رسومات التقاطع الهندسي

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

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