مجمع الاستقلال

مُركّب الاستقلال للرسم البياني هو كائن رياضي يصف المجموعات المستقلة في الرسم البياني. رسميًا، مُركّب الاستقلال للرسم البياني غير الموجّه G ، ويُرمز له بـ I( G )، هو مُركّب تبسيطي مُجرّد (أي عائلة من المجموعات المنتهية المغلقة تحت عملية أخذ المجموعات الجزئية)، يتكوّن من مجموعات الرؤوس في المجموعات المستقلة لـ G. أي مجموعة جزئية من مجموعة مستقلة هي نفسها مجموعة مستقلة، لذا فإن I( G ) مغلق بالفعل تحت عملية أخذ المجموعات الجزئية.

كل مجموعة مستقلة في رسم بياني تُشكّل زمرة في الرسم البياني المُكمّل له ، والعكس صحيح. لذلك، فإن مُركّب الاستقلال في رسم بياني ما يُساوي مُركّب الزمر في الرسم البياني المُكمّل له، والعكس صحيح.

درس العديد من المؤلفين العلاقات بين خصائص الرسم البياني G = ( V , E ) ومجموعات التماثل لمركب الاستقلال I( G ). ^{[ 1 ]} وعلى وجه الخصوص، تضمن العديد من الخصائص المتعلقة بالمجموعات المهيمنة في G أن بعض مجموعات التماثل المختزلة لـ I( G ) تكون تافهة.

1. العدد الإجمالي للهيمنة في G، ويرمز له بـ${\displaystyle \gamma _{0}(G)}$، هو الحد الأدنى لعدد عناصر مجموعة مهيمنة كلية في G - وهي مجموعة S بحيث يكون كل رأس من V مجاورًا لرأس من S.${\displaystyle \gamma _{0}(G)>k}$ثم${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$[ ^{2 ]​}

2. عدد الهيمنة الكلي لمجموعة جزئية A من V في G، ويرمز له بـ${\displaystyle \gamma _{0}(G,A)}$، هو الحد الأدنى لعدد عناصر المجموعة S بحيث يكون كل رأس من رؤوس A مجاورًا لرأس من رؤوس S. ويُرمز إلى عدد هيمنة الاستقلال للمجموعة G بالرمز .${\displaystyle i\gamma (G)}$، هي القيمة القصوى، على جميع المجموعات المستقلة A في G ، من ${\displaystyle \gamma _{0}(G,A)}$. لو ${\displaystyle i\gamma (G)>k}$، ثم${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$[ ^{1 ] [ 3 ]​}

3. عدد الهيمنة لـ G ، ويرمز له بـ${\displaystyle \gamma (G)}$، هو الحد الأدنى لعدد عناصر المجموعة المهيمنة على G - وهي مجموعة S بحيث يكون كل رأس من V \ S مجاورًا لرأس من S. لاحظ أن${\displaystyle \gamma _{0}(G)\geq \gamma (G)}$إذا كان G رسمًا بيانيًا وتريًا و${\displaystyle \gamma (G)>k}$ثم${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$[ ^{4 ]​}

4. عدد المطابقة المستحث لـ G ، ويرمز له بـ${\displaystyle \mu (G)}$، هي أكبر عدد من العناصر في مطابقة مستحثة في G - وهي مطابقة تشمل كل حافة تربط أي رأسين في المجموعة الجزئية. إذا وُجدت مجموعة جزئية A من V بحيث${\displaystyle \gamma _{0}(G,A)>k+\min[k,\mu (G[A])]}$ثم${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$[ ^{5 ]} هذا تعميم لكل من الخاصيتين 1 و2 أعلاه ^.

5. مُركّب الاستقلال غير المُهيمن لـ G، ويُرمز له بـ I'( G )، هو المُركّب التبسيطي المُجرّد للمجموعات المُستقلة التي ليست مجموعات مُهيمنة لـ G. من الواضح أن I'( G ) مُحتوى في I( G )؛ ولنرمز إلى خريطة التضمين بـ${\displaystyle i:I'(G)\to I(G)}$إذا كان G رسمًا بيانيًا وتريًا، فإن الخريطة المستحثة${\displaystyle i_{*}:{\tilde {H}}_{k}(I'(G))\to {\tilde {H}}_{k}(I(G))}$الصفر للجميع${\displaystyle k\geq -1}$. ^{[ 1 ] : Thm.1.4} هذا تعميم للخاصية 3 أعلاه.

6. عدد هيمنة النجوم الجزئية لـ G، ويرمز له بـ${\displaystyle \gamma _{s}^{*}(G)}$، هو الحد الأدنى لحجم مجموعة النجوم المهيمنة الجزئية في G. إذا${\displaystyle \gamma _{s}^{*}(G)>k}$ثم${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$[ ^{1 ] : نظرية 1.5}

لعبة ميشولام هي لعبة يتم لعبها على الرسم البياني G ، والتي يمكن استخدامها لحساب الحد الأدنى للاتصال المتجانس لمجموعة الاستقلال الخاصةبـ G.

إنّ مُركّب المطابقة للرسم البياني G ، والذي يُرمز له بـ M( G )، هو مُركّب تبسيطي مُجرّد للمطابقات في G. وهو مُركّب الاستقلال للرسم البياني الخطي لـ G. ^{[ 6 ] [ 7 ]}

مُركّب رقعة الشطرنج ( m , n ) هو مُركّب المطابقة على الرسم البياني الثنائي الكامل K _m , _n . وهو مُركّب تبسيطي مُجرّد لجميع مجموعات المواضع على رقعة شطرنج m × n ، والتي يُمكن وضع الرخّات عليها دون أن يُهدّد أيٌّ منها الآخر. ^{[ 8 ] [ 9 ]}

إن مجموعة الزمر في G هي مجموعة الاستقلال للرسم البياني المكمل لـ G.

• مجموعة مستقلة عن قوس قزح