مرجع
آخر الزيارات

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

1٬101 كلمة•0 مشاهدة•🗒️ منذ 17 يوماً
باختصار: في نظرية الرسم البياني، نعرف مجموعة مستقلة أومجموعة مستقرة (stable set أو independent set) بأنها مجموعة من رؤوس رسم بياني والتي كل رأسين بها هما غير متجاوران. تجد هنا «مجموعات مستقلة قصوى وأكبر تجمعات»، «العلاقة مع غيرها من متغيرات الرسم البياني» و«إيجاد أكبر المجموعات مستقلة» ضمن 7 أقسام.
المحتويات
  1. مجموعات مستقلة قصوى وأكبر تجمعات
  2. العلاقة مع غيرها من متغيرات الرسم البياني
  3. إيجاد أكبر المجموعات مستقلة
  4. مجموعة مستقلة قصوى
  5. الخوارزميات الدقيقة
  6. الحصول على مجموعات مستقلة
  7. خوارزميات التقريب
مجموعة مستقلة (نظرية الرسومات)

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

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

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

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

الخصائص

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

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

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

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

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

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

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

وفي هذا السياق، تعتبر مسألة تلوين رؤوس الرسم البياني G تجزئة (partition) لمجموعة رؤوس G إلى مجموعات جزئية مستقلة. ومن هنا يكون الحد الأدنى لعدد الألوان المطلوبة في تلوين الرؤوس، المعروف بالعدد اللوني ، هو على الأقل حاصل قسمة عدد الرؤوس في والرقم المستقل .

وفي هذا السياق، نقول أن المجموعة مستقلة إذا وفقط إذا كانت تجمع (Clique) في تكملة الرسم البياني، وبالتالي فإن المفهومين متكاملان. في الواقع، تحتوي الرسوم البيانية الكبيرة التي ليس لها عصابات كبيرة على مجموعات كبيرة مستقلة، والذي يتم دراسته في نظرية رامزي (Ramsey theory).

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

برنامج للبحث عن أقصى مجموعة مستقلة

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

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

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

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

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

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

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

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

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

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

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

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

من جانب آخر، في مسألة المجموعة المستقلة القصوى ، يكون المعطيات هنا عبارة عن رسم بياني غير موجه، والناتج هو مجموعة مستقلة قصوى في الرسم البياني. إذا كان هناك عدة مجموعات مستقلة قصوى، فالمطلوب هنا مجموعة واحدة فقطاجة واحدة فقط. يشار إلى هذه المسألة أحيانًا باسم " vertex packing ".

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

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

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

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.