مجموعة مستقلة (نظرية الرسومات)
{{يتيمة|تاريخ=سبتمبر 2019}}
[[ملف:Independent_set_graph.svg|تصغير|هنا تسع رؤوس زرقاء تشكل أكبر مجموعة مستقلة للرسم البياني بيترسين المعمم <math>GP(12,4)</math> .]]
في [[نظرية البيان|نظرية الرسم البياني]]، نعرف '''مجموعة مستقلة''' أومجموعة '''مستقرة''' ('''stable set''' أو '''independent set''') بأنها مجموعة من [[رأس (نظرية المخططات)|رؤوس]] [[رسم بياني]] والتي كل رأسين بها هما غير متجاوران. بمعنى آخر، المجموعة المستقلة هي مجموعة ''S'' من الرؤوس بحيث لا يوجد ضلع يربط بين كل رأسين في ''S.'' وهذا يعني أن كل ضلع في الرسم البياني له رأس واحد عالأكثر واحدة على الأكثر في ''S.'' حجم المجموعة المستقلة هو عدد الرؤوس بها. تسمى المجموعات المستقلة أيضا ب'''مجموعات مستقرة داخليا'''.<ref>{{Harvard citation text|Korshunov|1974}}</ref>

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

'''تعرف المجموعة المستقلة القصوى''' بشكل آخر بأنها '''مجموعة''' مستقلة والتي لها أكبر حجم ممكن للرسم البياني ''G'' المحدد. يُسمى هذا الرقم بعدد '''الاستقلال (independence)''' لـ ''G'' ، ويرمز بالرمز <math>\alpha(G)</math>.<ref>{{Harvard citation text|Godsil|Royle|2001}}, p. 3.</ref> تعتبر مسألة إيجاد المجموعة المستقلة القصوى مشكلة من النوع [[مسائل NP صعبة|NP-hard]] بمسائل الأمثلية. فبالتالي فإنه من غير المحتمل وجود خوارزمية فعالة لإيجاد الحد الأقصى المستقل لمجموعة من الرسم البياني.

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

== الخصائص ==

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

أيضا يقال أن المجموعة مستقلة إذا وفقط إذا كان المكمل لها يمثل غطاء الرأس.<ref>PROOF: A set V of vertices is an independent set IFF every edge in the graph is adjacent to at most one member of V IFF every edge in the graph is adjacent to at least one member not in V IFF the complement of V is a vertex cover.</ref> لذلك فإن مجموع حجم أكبر مجموعة مستقلة <math>\alpha(G)</math> وحجم الحد الأدنى من غطاء الرأس <math>\beta(G)</math> يساوي عدد الرؤوس في الرسم البياني <math>V(G)</math>، أي أن <math>\alpha(G)+\beta(G)=V(G)</math>.

تعتبر مسألة [[مسألة تلوين المخطط|تلوين رؤوس]] الرسم البياني ''G'' تجزئة ([[:en:Partition of a set|partition]]) لمجموعة رؤوس ''G'' إلى مجموعات جزئية مستقلة. ومن هنا يكون الحد الأدنى لعدد الألوان المطلوبة في تلوين الرؤوس، المعروف '''بالعدد اللوني''' <math>\mathcal X(G)</math>، هو على الأقل حاصل قسمة عدد الرؤوس في <math>G</math> والرقم المستقل <math>\alpha (G)</math>.

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

=== مجموعة مستقلة قصوى ===
تسمى المجموعة المستقلة التي ليس لها مجموعات جزئية بمجموعة مستقلة أخرى بأنها مجموعة قصوى. هذه المجموعات هي مجموعات مسيطرة. يحتوي كل رسم بياني على من <math>3^{n/3}</math> على الأكثر من المجموعات المستقلة القصوى <ref>{{Harvard citation text|Moon|Moser|1965}}.</ref> لكن العديد من الرسوم البيانية تحتوي على أقل من ذلك العدد بكثير. يتم الحصول على عدد المجموعات المستقلة القصوى في الرسوم البيانية لدورة به <math>n</math> من الرؤوس بواسطة أرقام Perrin ، ويتم إستنتاج عدد المجموعات المستقلة القصوى في الرسوم البيانية لمسار به <math>n</math> من الرؤوس بواسطة تسلسل Padovan .<ref>{{Harvard citation text|Füredi|1987}}.</ref> لذلك، يتناسب كلا الرقمين مع قوى [[عدد بلاستيكي|الرقم البلاستيكي]] 1.324718 .

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

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

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

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

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

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

==== الخوارزميات الدقيقة ====
مسألة إيجاد مجموعة مستقلة قصوى هي [[مسائل NP صعبة|NP-hard]]. ومع ذلك، يمكن حلها بشكل أكثر كفاءة بزمن <math>O(2^n \, n^2 )</math> باستخدام [[بحث شامل|خوارزمية القوة الغاشمة]] التي تدرس كل [[مجموعة جزئية]] من الرؤوس والتحقق ما إذا كانت مجموعة مستقلة ام لا.

في عام 2017، تمكن حلها بزمن <math>O(1.1996^n )</math> باستخدام مساحة [[متعددة الحدود]].<ref>{{Harvard citation text|Xiao|Nagamochi|2017}}</ref> عند الاقتصار على الرسوم البيانية والذي به أقصى درجة هي 3، فيمكن حلها بزمن قدره <math>O(1.0836^n )</math>.<ref>{{Harvard citation text|Xiao|Nagamochi|2013}}</ref>

بالنسبة للعديد من فئات الرسوم البيانية، يمكن العثور على مجموعة مستقلة للوزن الأقصى بزمن متعدد الحدود. مثال على ذلك الرسوم البيانية الخالية من المخلب و <ref>{{Harvard citation text|Minty|1980}},{{Harvard citation text|Sbihi|1980}},{{Harvard citation text|Nakamura|Tamura|2001}},{{Harvard citation text|Faenza|Oriolo|Stauffer|2014}},{{Harvard citation text|Nobili|Sassano|2015}}</ref> الرسوم البيانية خالية من <math>P_5</math> <ref>{{Harvard citation text|Lokshtanov|Vatshelle|Villanger|2014}}</ref> والرسوم البيانية المثالية.<ref>{{Harvard citation text|Grötschel|Lovász|Schrijver|1988}}</ref> بالنسبة للرسوم البيانية الوتريه فيمكن الحصول على مجموعة مستقلة موزونه قصوى بزمن خطي.<ref>{{Harvard citation text|Frank|1976}}</ref>

التحلل المعياري هو أداة جيدة لحل مسألة ايجاد مجموعة مستقلة موزونه قصوى؛ خوارزمية الوقت الخطي على الرسوم البيانية هي المثال الأساسي لذلك. أداة أخرى مهمة هي فواصل التجمع (Clique separator) كما وصفها تارجان.<ref>{{Harvard citation text|Tarjan|1985}}</ref>

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

==== خوارزميات التقريب ====
بشكل عام، لا يمكن تقريب مسألة إيجاد مجموعة مستقلة قصوى إلى عدد ثابت في كثيرة حدود (ما لم تكن P = NP). في الواقع، فإن أقصى مجموعة مستقلة بشكل عام عبارة عن Poly-APX-Complete ، مما يعني أنه صعب مثل أي مشكلة يمكن تقريبها إلى عامل متعدد الحدود.<ref>{{استشهاد بدورية محكمة|الأخير=Bazgan|الأول=Cristina|الأخير2=Escoffier|الأول2=Bruno|الأخير3=Paschos|الأول3=Vangelis Th.|عنوان=Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness|صحيفة=Theoretical Computer Science|تاريخ=2005|المجلد=339|العدد=2–3|صفحات=272–292|DOI=10.1016/j.tcs.2005.03.007}}</ref> بالرغم من ذلك، هناك خوارزميات تقريب فعالة لفئات محدودة من الرسوم البيانية.

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

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

=== إيجاد أكبر المجموعات مستقلة ===
يمكن حل مسألة إيجاد مجموعة مستقلة قصوى بزمن [[تعقيد الوقت|متعدد الحدود]] باستخدام [[خوارزمية جشعة]] ([[:en:Greedy algorithm|greedy]] ) تافهة.<ref>{{Harvard citation text|Luby|1986}}.</ref> يمكن العثور على جميع المجموعات المستقلة القصوى في زمن قدره <math>O(3^{n/3})=O(1.4423^n)</math>.

== برنامج للبحث عن أقصى مجموعة مستقلة ==
{| class="wikitable"
! اسم 
! رخصة 
! لغة واجهة برمجة التطبيقات 
! معلومات موجزة 
|-
| [http://igraph.sourceforge.net/doc/html/ch15s02.html igraph] 
| [[رخصة جنو العمومية|GPL]] 
|C, Python, R, Ruby
| الحل الدقيق. "تم نقل التطبيق الحالي إلى رسم من مكتبة Very Nauty Graph Library بواسطة Keith Briggs ويستخدم الخوارزمية من الورقة S. Tsukiyama و M. Ide و H. Ariyoshi و I. Shirawaka. خوارزمية جديدة لتوليد كل المجموعات المستقلة القصوى SIAM J Computing، 6: 505-517، 1977 ". 
|-
| NetworkX 
| [[رخص بي إس دي|BSD]] 
|Python
| الحل التقريبي، راجع الروتين [https://networkx.github.io/documentation/stable/reference/algorithms/approximation.html#module-networkx.algorithms.approximation.independent_set maximum_independent_set] 
|}

== انظر أيضا ==

* مجموعة مستقلة من الأضلاع هي عبارة عن مجموعة من الأضلاع التي ب لا يوجد أضلاع مشتركة بين أي ضلعين بهذه المجموعة. وتعرف هذه المجموعة باسم [[المطابقة (نظرية الرسوم البيانية)|مطابقة]] ([[:en:Matching (graph theory)|matching]] ).
* تعتبر مسألة [[مسألة تلوين المخطط|تلوين الرؤوس]] تجزئة لمجموعة الرؤوس إلى مجموعات مستقلة.

== ملاحظات ==
{{مراجع|2}}

== المراجع ==
{{بداية المراجع|2}}
* {{استشهاد|الأول=Brenda S.|الأخير=Baker|مؤلف-وصلة=Brenda Baker|عنوان=Approximation algorithms for NP-complete problems on planar graphs|صحيفة=[[Journal of the ACM]]|المجلد=41|العدد=1|سنة=1994|صفحات=153–180|doi=10.1145/174644.174650}}.
* {{استشهاد|الأول1=Piotr|الأخير1=Berman|الأول2=Toshihiro|الأخير2=Fujito|الفصل=On approximation properties of the Independent set problem for degree 3 graphs|عنوان=Workshop on Algorithms and Data Structures|سنة=1995|صفحات=449–460|doi=10.1007/3-540-60220-8_84|المجلد=955|سلسلة=Lecture Notes in Computer Science|ناشر=[[شبرينغر|سبرنجر]]|isbn=978-3-540-60220-0|وصلة العنوان=Workshop on Algorithms and Data Structures}}.
* {{استشهاد|الأخير1=Berman|الأول1=Piotr|الأخير2=Karpinski|الأول2=Marek|الفصل=On some tighter inapproximability results|ناشر=[[شبرينغر|سبرنجر]]|سلسلة=[[Lecture Notes in Computer Science]]|عنوان=Automata, Languages and Programming, 26th International Colloquium, ICALP'99 Prague|المجلد=1644|صفحات=200–209|سنة=1999|doi=10.1007/3-540-48523-6|مكان=Prague|isbn=978-3-540-66224-2}}
* {{استشهاد|الأخير1=Bourgeois|الأول1=Nicolas|الأخير2=Escoffier|الأول2=Bruno|الأخير3=Paschos|الأول3=Vangelis Th.|الأخير4=van Rooij|الأول4=Johan M. M.|الفصل=A bottom-up method and fast algorithms for MAX INDEPENDENT SET|doi=10.1007/978-3-642-13731-0_7|مكان=Berlin|mr=2678485|صفحات=62–73|ناشر=Springer|سلسلة=Lecture Notes in Computer Science|عنوان=Algorithm theory—SWAT 2010|المجلد=6139|سنة=2010|isbn=978-3-642-13730-3|bibcode=2010LNCS.6139...62B|وصلة العنوان=SWAT and WADS conferences}}.
* {{استشهاد|doi=10.1016/s0196-6774(02)00294-8|الأخير1=Chan|الأول1=T. M.|مؤلف1-وصلة=Timothy M. Chan|سنة=2003|عنوان=Polynomial-time approximation schemes for packing and piercing fat objects|صحيفة=Journal of Algorithms|المجلد=46|العدد=2|صفحات=178–189|jstor=|مسار=|صيغة=|تاريخ الوصول=|citeseerx=10.1.1.21.5344}}.
* {{استشهاد|الأخير1=Chan|الأول1=T. M.|مؤلف1-وصلة=Timothy M. Chan|الأخير2=Har-Peled|الأول2=S.|مؤلف2-وصلة=Sariel Har-Peled|doi=10.1007/s00454-012-9417-5|عنوان=Approximation algorithms for maximum independent set of pseudo-disks|صحيفة=Discrete & Computational Geometry|المجلد=48|العدد=2|صفحات=373|سنة=2012|pmid=|pmc=|arxiv=1103.1431|citeseerx=10.1.1.219.2131}}.
* {{استشهاد|الأول1=N.|الأخير1=Chiba|الأول2=T.|الأخير2=Nishizeki|مؤلف2-وصلة=Takao Nishizeki|عنوان=Arboricity and subgraph listing algorithms|صحيفة=[[SIAM Journal on Computing]]|المجلد=14|العدد=1|صفحات=210–223|سنة=1985|doi=10.1137/0214017}}.
* {{استشهاد|الأخير1=Erlebach|الأول1=T.|الأخير2=Jansen|الأول2=K.|الأخير3=Seidel|الأول3=E.|doi=10.1137/s0097539702402676|عنوان=Polynomial-Time Approximation Schemes for Geometric Intersection Graphs|صحيفة=SIAM Journal on Computing|المجلد=34|العدد=6|صفحات=1302|سنة=2005|pmid=|pmc=}}.
* {{استشهاد|الأخير1=Faenza|الأول1=Y.|الأخير2=Oriolo|الأول2=G.|الأخير3=Stauffer|الأول3=G.|عنوان=Solving the Weighted Stable Set Problem in Claw-Free Graphs|صحيفة=Journal of the ACM|المجلد=61|العدد=4|صفحات=1–41|سنة=2014|doi=10.1145/2629600}}.
* {{استشهاد|الأخير1=Fomin|الأول1=Fedor V.|الأخير2=Grandoni|الأول2=Fabrizio|الأخير3=Kratsch|الأول3=Dieter|عنوان=A measure & conquer approach for the analysis of exact algorithms|صحيفة=Journal of the ACM|المجلد=56|سنة=2009|صفحات=1–32|العدد=5|doi=10.1145/1552285.1552286|postscript=, article&nbsp;no.&nbsp;25}}.
* {{استشهاد|الأخير=Frank|الأول=Andras|عنوان=Some polynomial algorithms for certain graphs and hypergraphs|صحيفة=Congressus Numerantium|المجلد=XV|صفحات=211–226|سنة=1976}}.
* {{استشهاد|الأخير=Füredi|الأول=Z.|مؤلف-وصلة=Zoltán Füredi|عنوان=The number of maximal independent sets in connected graphs|صحيفة=Journal of Graph Theory|المجلد=11|العدد=4|سنة=1987|صفحات=463–470|doi=10.1002/jgt.3190110403}}.
* {{استشهاد|الأخير1=Godsil|الأول1=Chris|مؤلف1-وصلة=Chris Godsil|الأخير2=Royle|الأول2=Gordon|مؤلف2-وصلة=Gordon Royle|عنوان=Algebraic Graph Theory|ناشر=[[شبرينغر|سبرنجر]]|سنة=2001|مكان=New York|isbn=978-0-387-95220-8}}.
* {{استشهاد|الأول=Martin|الأخير=Grohe|مؤلف-وصلة=Martin Grohe|عنوان=Local tree-width, excluded minors, and approximation algorithms|صحيفة=[[Combinatorica]]|المجلد=23|العدد=4|سنة=2003|doi=10.1007/s00493-003-0037-9|صفحات=613–632|arxiv=math/0001128}}.
* {{استشهاد|الأول1=M.|الأخير1=Grötschel|مؤلف1-وصلة=Martin Grötschel|الأول2=L.|الأخير2=Lovász|مؤلف2-وصلة=László Lovász|الأول3=A.|الأخير3=Schrijver|مؤلف3-وصلة=Alexander Schrijver|عنوان=Geometric Algorithms and Combinatorial Optimization|سلسلة=Algorithms and Combinatorics|المجلد=2|ناشر=[[شبرينغر|سبرنجر]]|سنة=1988|الفصل=9.4 Coloring Perfect Graphs|صفحات=296–298|isbn=978-0-387-13624-0}}.
* {{استشهاد|الأول1=M. M.|الأخير1=Halldórsson|الأول2=J.|الأخير2=Radhakrishnan|عنوان=Greed is good: Approximating independent sets in sparse and bounded-degree graphs|صحيفة=[[Algorithmica]]|المجلد=18|العدد=1|سنة=1997|صفحات=145–163|doi=10.1007/BF02523693|citeseerx=10.1.1.145.4523}}.
* {{استشهاد|الأخير=Korshunov|الأول=A.D.|لغة=Ukrainian|العدد=1|صحيفة=Kibernetika|صفحات=17–28|عنوان=Coefficient of Internal Stability|المجلد=10|سنة=1974|doi=10.1007/BF01069014}}.
* {{استشهاد|الأخير1=Lokshtanov|الأول1=D.|الأخير2=Vatshelle|الأول2=M.|الأخير3=Villanger|الأول3=Y.|صحيفة=[[SODA (Symposium on Discrete Algorithms)]]|صفحات=570–581|عنوان=Independent sets in ''P''<sub>5</sub>-free graphs in polynomial time|سنة=2014}}.
* {{استشهاد|الأخير=Luby|الأول=Michael|مؤلف-وصلة=Michael Luby|doi=10.1137/0215074|العدد=4|صحيفة=[[SIAM Journal on Computing]]|mr=861369|صفحات=1036–1053|عنوان=A simple parallel algorithm for the maximal independent set problem|المجلد=15|سنة=1986}}.
* {{استشهاد|الأخير=Minty|الأول=G.J.|صحيفة=[[Journal of Combinatorial Theory, Series B]]|صفحات=284–304|عنوان=On maximal independent sets of vertices in claw-free graphs|المجلد=28|العدد=3|سنة=1980|doi=10.1016/0095-8956(80)90074-x}}.
* {{استشهاد|الأول1=J.W.|الأخير1=Moon|الأول2=Leo|الأخير2=Moser|مؤلف2-وصلة=Leo Moser|عنوان=On cliques in graphs|صحيفة=Israel Journal of Mathematics|المجلد=3|سنة=1965|العدد=1|صفحات=23–28|mr=0182577|doi=10.1007/BF02760024}}.
* {{استشهاد|الأخير1=Nakamura|الأول1=D.|الأخير2=Tamura|الأول2=A.|صحيفة=[[Journal of Operations Research Society Japan]]|صفحات=194–204|عنوان=A revision of Minty's algorithm for finding a maximum weight stable set in a claw-free graph|المجلد=44|سنة=2001}}.
* {{استشهاد|الأخير1=Nobili|الأول1=P.|الأخير2=Sassano|الأول2=A.|عنوان=An O(n^2 log n) algorithm for the weighted stable set problem in claw-free graphs|arxiv=1501.05775|سنة=2015|bibcode=2015arXiv150105775N}}
* {{استشهاد|الأول=J. M.|الأخير=Robson|عنوان=Algorithms for maximum independent sets|صحيفة=Journal of Algorithms|المجلد=7|سنة=1986|صفحات=425–440|العدد=3|doi=10.1016/0196-6774(86)90032-5}}.
* {{استشهاد|الأخير=Sbihi|الأول=Najiba|doi=10.1016/0012-365X(90)90287-R|لغة=French|العدد=1|صحيفة=Discrete Mathematics|صفحات=53–76|عنوان=Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile|المجلد=29|سنة=1980|mr=553650}}.
* {{استشهاد|الأخير1=Xiao|الأول1=Mingyu|الأخير2=Nagamochi|الأول2=Hiroshi|صحيفة=[[Information and Computation]]|صفحات=126–146|عنوان=Exact algorithms for maximum independent set|المجلد=255|سنة=2017|doi=10.1016/j.ic.2017.06.001|arxiv=1312.6260}}.
* {{استشهاد|الأخير1=Xiao|الأول1=Mingyu|الأخير2=Nagamochi|الأول2=Hiroshi|صحيفة=[[علم الحاسوب النظري]]|صفحات=92–104|عنوان=Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs|المجلد=469|سنة=2013|doi=10.1016/j.tcs.2012.09.022}}.
* {{استشهاد|الأخير=Tarjan|الأول=R.E.|مؤلف-وصلة=Robert Endre Tarjan|عنوان=Decomposition by clique separators|صحيفة=Discrete Mathematics|المجلد=55|العدد=2|صفحات=221–232|سنة=1985|doi=10.1016/0012-365x(85)90051-2}}.
{{نهاية المراجع}}

== روابط خارجية ==

* {{ماثوورلد|urlname=MaximalIndependentVertexSet|title=Maximal Independent Vertex Set}}
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring]
* [http://www.hananayad.com/teaching/syde423/IndependentSet.pdf Independent Set and Vertex Cover], Hanan Ayad.
<nowiki>
</nowiki>
{{روابط شقيقة|commons=Independent set (graph theory)}}
{{شريط بوابات|رياضيات|علم الحاسوب}}

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

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

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

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

 الخصائص 

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

أيضا يقال أن المجموعة مستقلة إذا وفقط إذا كان المكمل لها يمثل غطاء الرأس.PROOF: A set V of vertices is an independent set IFF every edge in the graph is adjacent to at most one member of V IFF every edge in the graph is adjacent to at least one member not in V IFF the complement of V is a vertex cover. لذلك فإن مجموع حجم أكبر مجموعة مستقلة  وحجم الحد الأدنى من غطاء الرأس  يساوي عدد الرؤوس في الرسم البياني ، أي أن .

تعتبر مسألة تلوين رؤوس الرسم البياني 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 ) تافهة.. يمكن العثور على جميع المجموعات المستقلة القصوى في زمن قدره .

 برنامج للبحث عن أقصى مجموعة مستقلة 
 اسم  رخصة  لغة واجهة برمجة التطبيقات  معلومات موجزة  igraph  GPL C, Python, R, Ruby الحل الدقيق. "تم نقل التطبيق الحالي إلى رسم من مكتبة Very Nauty Graph Library بواسطة Keith Briggs ويستخدم الخوارزمية من الورقة S. Tsukiyama و M. Ide و H. Ariyoshi و I. Shirawaka. خوارزمية جديدة لتوليد كل المجموعات المستقلة القصوى SIAM J Computing، 6: 505-517، 1977 ".  NetworkX  BSD Python الحل التقريبي، راجع الروتين maximum_independent_set 

 انظر أيضا 

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

 ملاحظات 

 المراجع 

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

 روابط خارجية 

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

تصنيف:رياضيات
تصنيف:مسائل كثيرة حدود غير قطعية كاملة