مجموعة توليد قوية

في الجبر المجرد ، وخاصة في مجال نظرية الزمر ، تُعرَّف المجموعة المولدة القوية لزمرة التبديل بأنها مجموعة مولدة تُظهر بوضوح بنية التبديل كما هو موضح بسلسلة مثبتة . السلسلة المثبتة هي سلسلة من الزمر الجزئية ، تحتوي كل منها على الزمرة التي تليها، وتُثبِّت كل منها نقطة إضافية.

يترك${\displaystyle G\leq S_{n}}$لتكن مجموعة من تباديل المجموعة${\displaystyle \{1,2,\ldots ,n\}.}$ يترك

${\displaystyle B=(\beta _{1},\beta _{2},\ldots ,\beta _{r})}$

لتكن سلسلة من الأعداد الصحيحة المختلفة ،${\displaystyle \beta _{i}\in \{1,2,\ldots ,n\},}$بحيث يكون المثبت النقطي لـ${\displaystyle B}$هو أمر تافه (أي، ليكن${\displaystyle B}$كن قاعدة لـ${\displaystyle G}$). يُعرِّف

${\displaystyle B_{i}=(\beta _{1},\beta _{2},\ldots ,\beta _{i}),\,}$

وحدد${\displaystyle G^{(i)}}$ليكون المثبت النقطي لـ${\displaystyle B_{i}}$مجموعة توليد قوية (SGS) للرسم البياني G بالنسبة للأساس${\displaystyle B}$هي مجموعة

${\displaystyle S\subseteq G}$

بحيث

${\displaystyle \langle S\cap G^{(i)}\rangle =G^{(i)}}$

لكل${\displaystyle i}$بحيث${\displaystyle 1\leq i\leq r}$.

يُقال إن القاعدة ونظام SGS غير متكررين إذا

${\displaystyle G^{(i)}\neq G^{(j)}}$

ل${\displaystyle i\neq j}$.

يمكن حساب مجموعة أساسية ومجموعة توليد قوية (BSGS) لمجموعة باستخدام خوارزمية Schreier–Sims .

• أ. سيريس، خوارزميات مجموعة التبديل ، مطبعة جامعة كامبريدج، 2002.