تقسيم ماترويد

في الرياضيات، الماترويد التقسيمي هو ماترويد يُمثل مجموعًا مباشرًا لماترويدات منتظمة . ^{[ 1 ]} يُعرَّف على مجموعة أساسية تُقسَّم عناصرها إلى فئات مختلفة. لكل فئة، يوجد قيد سعة - وهو الحد الأقصى لعدد العناصر المسموح بها من هذه الفئة. المجموعات المستقلة للماترويد التقسيمي هي تحديدًا المجموعات التي يكون فيها عدد العناصر من كل فئة، على الأكثر، مساويًا لسعة تلك الفئة.

يترك${\displaystyle C_{i}}$لتكن مجموعة من المجموعات المنفصلة ("الفئات").${\displaystyle d_{i}}$لتكن أعدادًا صحيحة${\displaystyle 0\leq d_{i}\leq |C_{i}|}$("السعات"). حدد مجموعة فرعية${\displaystyle I\subseteq \bigcup _{i}C_{i}}$أن تكون "مستقلة" عندما، لكل مؤشر${\displaystyle i}$،${\displaystyle |I\cap C_{i}|\leq d_{i}}$. تشكل المجموعات التي تحقق هذا الشرط المجموعات المستقلة للماترويد ، والتي تسمى ماترويد التقسيم .

المجموعات${\displaystyle C_{i}}$تُسمى هذه الفئات أو الكتل الخاصة بالمصفوفة التقسيمية.

أساس الماترويد التقسيمي هو مجموعة يكون تقاطعها مع كل كتلة${\displaystyle C_{i}}$حجمه بالضبط${\displaystyle d_{i}}$الدائرة في الماترويد هي مجموعة فرعية من كتلة واحدة${\displaystyle C_{i}}$بالحجم بالضبط${\displaystyle d_{i}+1}$رتبة الماترويد هي${\displaystyle \sum d_{i}}$[ ^{2 ]​}

كل ماترويد موحد${\displaystyle U{}_{n}^{r}}$هي مصفوفة تقسيم، ذات كتلة واحدة${\displaystyle C_{1}}$ل${\displaystyle n}$العناصر ومع${\displaystyle d_{1}=r}$كل مصفوفة تقسيم هي المجموع المباشر لمجموعة من المصفوفات المنتظمة، واحدة لكل كتلة من كتلها.

في بعض المنشورات، يتم تعريف مفهوم المصفوفة التقسيمية بشكل أكثر تقييدًا، مع كل${\displaystyle d_{i}=1}$. إن التقسيمات التي تخضع لهذا التعريف الأكثر تقييدًا هي المصفوفات المستعرضة لعائلة المجموعات المنفصلة المعطاة بواسطة كتلها. ^{[ 3 ]}

كما هو الحال مع الماترويدات المنتظمة التي تُشكَّل منها، فإن الماترويد الثنائي لماترويد التقسيم هو أيضاً ماترويد تقسيم، وكل مصغر لماترويد تقسيم هو أيضاً ماترويد تقسيم. والمجاميع المباشرة لماترويدات التقسيم هي أيضاً ماترويدات تقسيم.

التطابق الأقصى في الرسم البياني هو مجموعة من الحواف تكون بأكبر حجم ممكن بشرط ألا تشترك أي حافتين في نقطة نهاية واحدة. في الرسم البياني ثنائي الأجزاء مع التقسيم الثنائي${\displaystyle (U,V)}$، مجموعات الحواف التي تحقق الشرط الذي ينص على عدم اشتراك أي حافتين في نقطة نهاية واحدة${\displaystyle U}$هي المجموعات المستقلة لمصفوفة تقسيم تحتوي على كتلة واحدة لكل رأس في${\displaystyle U}$ومع كل رقم من الأرقام${\displaystyle d_{i}}$يساوي واحدًا. مجموعات الحواف التي تحقق الشرط الذي ينص على عدم اشتراك أي حافتين في نقطة نهاية واحدة في${\displaystyle V}$تمثل هذه المجموعات المستقلة مجموعة مصفوفة تقسيم ثانية. لذلك، يمكن تمثيل مسألة المطابقة القصوى الثنائية على أنها تقاطع مصفوفتين من هاتين المجموعتين. ^{[ 4 ]}

وبشكل أعم، يمكن تمثيل تطابقات الرسم البياني على أنها تقاطع بين ماترويدين إذا وفقط إذا كانت كل دورة فردية في الرسم البياني عبارة عن مثلث يحتوي على رأسين أو أكثر من الدرجة الثانية. ^{[ 5 ]}

مجموعة الزمر هي عائلة من مجموعات رؤوس الرسم البياني${\displaystyle G}$التي تُنتج رسومًا بيانية فرعية كاملة من${\displaystyle G}$يشكل مُركّب الزمرة مادةً إذا وفقط إذا${\displaystyle G}$هي رسم بياني متعدد الأجزاء كامل ، وفي هذه الحالة يكون الماترويد الناتج ماترويدًا تجزئة. مجمعات الزمر هي بالضبط أنظمة المجموعات التي يمكن تشكيلها كتقاطعات لعائلات من ماترويدات التجزئة التي يكون فيها كل${\displaystyle d_{i}=1}$[ ^{6 ]​}

عدد المصفوفات التقسيمية المتميزة التي يمكن تعريفها على مجموعة من${\displaystyle n}$العناصر المصنفة، لـ${\displaystyle n=0,1,2,\dots }$، يكون

1، 2، 5، 16، 62، 276، 1377، 7596، 45789، 298626، 2090910، ... (التسلسل A005387 في OEIS ) .

الدالة المولدة الأسية لهذه المتتالية هي${\displaystyle f(x)=\exp(e^{x}(x-1)+2x+1)}$[ ^{7 ]​}