مجموعة مستقلة (نظرية الرسومات)
في نظرية الرسم البياني، نعرف مجموعة مستقلة أومجموعة مستقرة (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 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

انظر أيضا 

 مجموعة مستقلة من الأضلاع هي عبارة عن مجموعة من الأضلاع التي ب لا يوجد أضلاع مشتركة بين أي ضلعين بهذه المجموعة. وتعرف هذه المجموعة باسم مطابقة (matching ).
 تعتبر مسألة تلوين الرؤوس تجزئة لمجموعة الرؤوس إلى مجموعات مستقلة.

ملاحظات

المراجع 

 .
 .
 
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 .
 
 .
 .
 .
 .
 .

روابط خارجية 

 
 Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring
 Independent Set and Vertex Cover, Hanan Ayad.

رياضيات
مسائل كثيرة حدود غير قطعية كاملة
في نظرية الرسم البياني ، نعرف مجموعة مستقلة أومجموعة مستقرة ( stable set أو independent set ) ب أن ها مجموعة من رؤوس رسم بياني و التي كل رأسين ب ها هما غير متجاوران . ب معنى آخر ، المجموعة المستقلة هي مجموعة S من ال رؤوس ب حيث لا يوجد ضلع يربط بين كل رأسين في S . و هٰذا يعني أن كل ضلع في الرسم البياني ل ه رأس واحد عالأكثر واحدة على الأكثر في S . حجم المجموعة المستقلة هو عدد ال رؤوس ب ها . تسمى المجموعات المستقلة أيضا بمجموعات مستقرة داخليا . المجموعة المستقلة القصوى ( maxim al independent set ) هي إما مجموعة مستقلة ب حيث أن إضافة أي رأس ل ها ينتج عن ه ضلع ينتمي ب الكامل ل هٰذه المجموعة أو مجموعة من جميع رؤوس الرسم البياني الخالي ( أي لا يحتوي على أضلاع ) . تعرف المجموعة المستقلة القصوى ب شكل آخر ب أن ها مجموعة مستقلة و التي ل ها أكبر حجم ممكن للرسم البياني G المحدد . يُسمى هذا الرقم ب عدد الاستقلال ( independence ) لـ G ، ويرمز بالرمز \ . تعتبر مسألة إيجاد المجموعة المستقلة القصوى مشكلة من النوع NP - h ard بمسائل الأمثلية . ف ب التالي ف إن ه من غير المحتمل وجود خوارزمية فعالة ل إيجاد الحد الأقصى المستقل ل مجموعة من الرسم البياني . كل مجموعة مستقلة قصوى هي أيضًا الحد الأقصى ، لكن العكس ليس دائما صحيح . الخصائص العلاقة مع غير ها من متغيرات الرسم البياني نقول أن المجموعة مستقلة إذا وفقط إذا كانت تجمع ( Clique ) في تكملة الرسم البياني ، و ب التالي ف إن المفهومين متكاملان . في الواقع ، تحتوي الرسوم البيانية الكبيرة التي ليس ل ها عصابات كبيرة على مجموعات كبيرة مستقلة ، و الذي يتم دراسة ه في نظرية رامزي ( Ramsey th eory ) . أيضا يقال أن المجموعة مستقلة إذا وفقط إذا كان المكمل ل ها يمثل غطاء الرأس . ل ذٰلك ف إن مجموع حجم أكبر مجموعة مستقلة و حجم الحد الأدنى من غطاء الرأس يساوي عدد ال رؤوس في الرسم البياني ، أي أن\ . تعتبر مسألة تلوين رؤوس الرسم البياني G تجزئة ( partition ) ل مجموعة رؤوس G إلى مجموعات جزئية مستقلة . و من هنا يكون الحد الأدنى ل عدد الألوان المطلوبة في تلوين ال رؤوس ، المعروف بالعدد اللوني ، هو على الأقل حاصل قسمة عدد ال رؤوس في و الرقم المستقل \ . في الـرسم ثنائي الأطراف أو التجزئة الذي لا يحتوي على أي رؤوس معزولة ، ف إن عدد الاستقلال يساوي عدد الأضلاع في الحد الأدنى لـغطاء الأضلاع ؛ هذه هي نظرية كونيج . مجموعة مستقلة قصوى تسمى المجموعة المستقلة التي ليس ل ها مجموعات جزئية بمجموعة مستقلة أخرى ب أن ها مجموعة قصوى . هذه المجموعات هي مجموعات مسيطرة . يحتوي كل رسم بياني على من على الأكثر من المجموعات المستقلة القصوى لكن العديد من الرسوم البيانية تحتوي على أقل من ذلك العدد ب كثير . يتم الحصول على عدد المجموعات المستقلة القصوى في الرسوم البيانية ل دورة ب ه من ال رؤوس ب واسطة أرقام Perrin ، و يتم إستنتاج عدد المجموعات المستقلة القصوى في الرسوم البيانية لمسار ب ه من ال رؤوس ب واسطة تسلسل Padovan\ . ل ذٰلك ، يتناسب كلا الرقمين مع قوى الرقم البلاستيكي 324718\ . الحصول على مجموعات مستقلة في علوم الكمبيوتر ، تمت دراسة العديد من المشكلات الحسابية المتعلقة بمجموعات مستقلة . في مسألة المجموعة المستقلة القصوى ، يكون المعطيات هنا عبارة عن رسم بياني غير موجه ، والناتج هو مجموعة مستقلة قصوى في الرسم البياني . إذا كان هناك عدة مجموعات مستقلة قصوى ، ف المطلوب هنا مجموعة واحدة فقطاجة واحدة فقط . يشار إلى هذه المسألة أحيانًا ب اسم " vertex packing " . في مسألة مجموعة مستقل ه موزون ه قصوى ، يكون المتطلب هنا عبارة عن رسم بياني غير موجه مع أوزان لرؤ ه و يكون الناتج مجموعة مستقلة ذات أقصى مجموع للأوزان . تعتبر مسألة المجموعة المستقلة القصوى حالة خاصة من المجموعة المستقلة الموزون ه القصوى و التي تكون في ها جميع الأوزان واحدة . في مسألة ال إدراج المستقل القصوى ، نحتاج ل رسم ب غير موجه ، و يتم البحث هنا عن قائمة ب جميع مجموعات ه المستقلة القصوى . يمكن حل هذه المسألة ب استخدام خوارزمية روتين فرعي ل مشكلة قائمة مجموعة الحد الأقصى المستقل ، لأن ه يجب تضمين مجموعة الحد الأقصى المستقل بين جميع مجموعات الحد الأقصى المستقل . مسألة قرار المجموعة المستقلة أيضا تتطلب رسم بياني غير موجه ورقم k ، و تهتم ب إيجاد قيمة منطقية و التي تكون صائبة في حالة احتواء الرسم البياني على مجموعة مستقلة من الحجم k ، وخاطئة فيما عدا ذلك . المسائل الثلاث الأولى المذكور ه أعلا ه مهمة في التطبيقات العملية . بينما مسألة قرار المجموعة المستقلة ليست كذلك لٰكن ها ضرورية من أجل تطبيق نظرية اكتمال NP على المشكلات المتعلقة ب المجموعات المستقلة . مجموعات مستقلة قصوى و أكبر تجمعات تعتبر مسألتي المجموعة المستقلة وال تجميع متكاملتين : فأي تجميع في G هو مجموعة مستقلة في الرسم البياني التكميلي لـ G و العكس صحيح . ل ذٰلك قد يتم تطبيق العديد من النتائج الحسابية ب شكل جيد على حد سواء ل هاتين المسألتين . على سبيل المثال ، تحتوي النتائج المرتبطة بمسألة ال تجميع على النتائج التالية : مسائل قرار مجموعة مستقلة هي NP - كاملة ، و ب التالي لا يعتقد أن هناك خوارزمية فعالة ل حل ها . مسائل المجموعة المستقلة القصوى هي من النوع NP - hard ف من الصعب أيضًا تقريب ها . إيجاد أكبر مجموعات مستقلة الخوارزميات الدقيقة مسألة إيجاد مجموعة مستقلة قصوى هي NP - h ard . و مع ذلك ، يمكن حل ها ب شكل أكثر كفاءة ب زمن ب استخدام خوارزمية القوة الغاشمة التي تدرس كل مجموعة جزئية من ال رؤوس والتحقق ما إذا كانت مجموعة مستقلة ام لا . في عام تمكن حل ها ب زمن ب استخدام مساحة متعددة الحدود . عند الاقتصار على الرسوم البيانية و الذي ب ه أقصى درجة هي ف يمكن حل ها ب زمن قدر ه \ . ب النسبة ل العديد من فئات الرسوم البيانية ، يمكن العثور على مجموعة مستقلة للوزن الأقصى ب زمن متعدد الحدود . مثال على ذلك الرسوم البيانية الخالية من المخلب و الرسوم البيانية خالية من و الرسوم البيانية المثالية . ب النسبة للرسوم البيانية الوتريه ف يمكن الحصول على مجموعة مستقلة موزون ه قصوى ب زمن خطي . التحلل المعياري هو أداة جيدة ل حل مسألة ايجاد مجموعة مستقلة موزون ه قصوى ؛ خوارزمية الوقت الخطي على الرسوم البيانية هي المثال الأساسي ل ذٰلك . أداة أخرى مهمة هي فواصل التجمع ( Clique separator ) كما وصف ها تارجان . في الرسم البياني ثنائي الأطراف ، يمكن تضمين جميع ال رؤوس غير الموجودة في الحد الأدنى من غطاء الرأس في مجموعة مستقلة قصوى و يمكن قراءة نظرية Kőnig لتفاصيل أكثر . ف ب التالي يمكن الحصول على الحد الأدنى من أغطية الرأس ب استخدام خوارزمية مطابقة ثنائية الطرف . خوارزميات ا التقريب ب شكل عام ، لا يمكن تقريب مسألة إيجاد مجموعة مستقلة قصوى إلى عدد ثابت في كثيرة حدود ( ما لم تكن P = NP ) . في الواقع ، ف إن أقصى مجموعة مستقلة ب شكل عام عبارة عن Poly - APX - Complete ، مما يعني أن ه صعب مثل أي مشكلة يمكن تقريب ها إلى عامل متعدد الحدود . ب الرغم من ذلك ، هناك خوارزميات تقريب فعالة ل فئات محدودة من الرسوم البيانية . مجموعات مستقلة في الرسوم البيانية تقاطع الفاصل مجموعات مستقلة في رسومات التقاطع الهندسي إيجاد أكبر المجموعات مستقلة يمكن حل مسألة إيجاد مجموعة مستقلة قصوى ب زمن متعدد الحدود ب استخدام خوارزمية جشعة ( greedy ) تافهة . يمكن العثور على جميع المجموعات المستقلة القصوى في زمن قدر ه \ . برنامج ل البحث عن أقصى مجموعة مستقلة انظر أيضا مجموعة مستقلة من الأضلاع هي عبارة عن مجموعة من الأضلاع التي ب لا يوجد أضلاع مشتركة بين أي ضلعين ب هٰذه المجموعة . و تعرف هذه المجموعة ب اسم مطابقة ( matching ) . تعتبر مسألة تلوين ال رؤوس تجزئة ل مجموعة ال رؤوس إلى مجموعات مستقلة . ملاحظات المراجع \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . \ . روابط خارجية C h allenging Bench m arks for Maximum Clique , Maximum Independent Set , Minimum Vertex Cover and Vertex Coloring Independent Set and Vertex Cover , Hanan A yad . رياضيات مسائل كثيرة حدود غير قطعية كاملة