رتبة ماترويد

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

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

في جميع الأمثلة، E هي المجموعة الأساسية للماترويد، و B هي مجموعة جزئية من E.

• ليكن M هو الماترويد الحر ، حيث تكون المجموعات المستقلة جميعها مجموعات جزئية من E. عندئذٍ تكون دالة الرتبة لـ M ببساطة: r ( B ) = | B |.
• ليكن M مصفوفة منتظمة ، حيث تكون المجموعات المستقلة هي المجموعات الجزئية من E التي تحتوي على k عنصر على الأكثر ، لعدد صحيح k . عندئذٍ تكون دالة رتبة M هي: r ( B ) = min( k , | B |).
• ليكن M مصفوفة تقسيمية : تُقسّم عناصر E إلى فئات، لكل فئة c سعة kc _، والمجموعات المستقلة هي تلك التي تحتوي على kc عنصرًا على الأكثر من الفئة _c . عندئذٍ _، تكون دالة رتبة M هي: r ( B ) = sum _c min( kc _, | Bc |) حيث Bc هي المجموعة الجزئية B الموجودة في الفئة c _.
• ليكن M عبارة عن مصفوفة رسومية ، حيث تكون المجموعات المستقلة هي جميع مجموعات الحواف غير الدورية ( الغابات ) لبعض الرسوم البيانية غير الموجهة الثابتة G. عندئذٍ تكون دالة الرتبة r ( B ) هي عدد الرؤوس في الرسم البياني ، مطروحًا منها عدد المكونات المتصلة لـ B (بما في ذلك مكونات الرأس الواحد).

تخضع دالة رتبة الماترويد للخصائص التالية.

(R1) قيمة دالة الرتبة هي دائمًا عدد صحيح غير سالب ورتبة المجموعة الفارغة هي 0.

(R2) لأي مجموعتين جزئيتين${\displaystyle A}$و${\displaystyle B}$ل${\displaystyle E}$،${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)}$أي أن الرتبة هي دالة مجموعة فرعية معيارية .

(R3) لأي مجموعة${\displaystyle A}$وعنصر${\displaystyle x}$،${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$.

يمكن استخدام هذه الخصائص كمسلمات لتوصيف دالة الرتبة للماترويدات: كل دالة مجموعة فرعية معيارية ذات قيم صحيحة على المجموعات الجزئية لمجموعة منتهية تحقق المتباينات التالية${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1}$للجميع${\displaystyle A}$و${\displaystyle x}$هي دالة الرتبة للماترويد. ^{[ 1 ] [ 2 ]}

تتضمن الخصائص المذكورة أعلاه خصائص إضافية:

• لو${\displaystyle A\subset B\subset E}$، ثم${\displaystyle r(A)\leq r(B)\leq r(E)}$أي أن الرتبة دالة رتيبة .
• ${\displaystyle r(A)\leq |A|}$.

يمكن استخدام دالة الرتبة لتحديد الخصائص المهمة الأخرى للماترويد:

• تكون المجموعة مستقلة إذا وفقط إذا كانت رتبتها تساوي عدد عناصرها، وتكون تابعة إذا وفقط إذا كان عدد عناصرها أكبر من رتبتها. ^{[ 3 ]}
• تُعتبر المجموعة غير الفارغة دائرة إذا كان عدد عناصرها يساوي واحدًا زائد رتبتها، وكانت كل مجموعة جزئية تتكون من إزالة عنصر واحد من المجموعة لها نفس الرتبة. ^{[ 3 ]}
• تُعتبر المجموعة أساسًا إذا كانت رتبتها تساوي كلًا من عدد عناصرها ورتبة الماترويد. ^{[ 3 ]}
• تكون المجموعة مغلقة إذا كانت ذات رتبة قصوى ، بمعنى أنه لا يوجد عنصر آخر يمكن إضافته إليها مع الحفاظ على نفس الرتبة.
• الفرق${\displaystyle |A|-r(A)}$يُطلق على ذلك اسم عدم وجود مجموعة جزئية${\displaystyle A}$هو الحد الأدنى لعدد العناصر التي يجب إزالتها من${\displaystyle A}$للحصول على مجموعة مستقلة. ^{[ 4 ]}
• الرتبة المشتركة لمجموعة جزئية${\displaystyle A}$يمكن أن يشير إلى كميتين مختلفتين على الأقل: يستخدمه بعض المؤلفين للإشارة إلى رتبة${\displaystyle A}$في الماترويد المزدوج ،${\displaystyle r^{*}(A)=|A|+r(E\setminus A)-r(E)}$بينما يستخدم مؤلفون آخرون مصطلح corank للإشارة إلى الفرق${\displaystyle r(E)-r(A)}$.

في نظرية المخططات ، يُعرف العدد الحلقي للمخطط بأنه رتبة المصفوفة الرسومية المرتبطة به ؛ وهو يقيس الحد الأدنى لعدد الحواف التي يجب إزالتها من المخطط لتكوين غابة من الحواف المتبقية. ^{[ 5 ]} وقد درس العديد من الباحثين التعقيد المُعامل لخوارزميات المخططات المُعاملة بهذا العدد. ^{[ 6 ] [ 7 ]}

في الجبر الخطي ، رتبة الماترويد الخطي المحدد بالاستقلال الخطي من أعمدة المصفوفة هي رتبة المصفوفة ، ^{[ 8 ]} وهي أيضًا بُعد الفضاء المتجهي الذي تمتده الأعمدة.

في الجبر المجرد ، تُعرف رتبة الماترويد المعرّفة من مجموعات العناصر في امتداد الحقل L / K بالاستقلال الجبري باسم درجة التجاوز . ^{[ 9 ]}

تُستخدم دوال رتبة الماترويد (MRF) لتمثيل دوال المنفعة للوكلاء في مسائل التوزيع العادل للعناصر . إذا كانت دالة منفعة الوكيل دالة رتبة الماترويد، فهذا يعني ما يلي:

• إن منفعة الوكيل لها عوائد متناقصة (وهذا يتبع من حقيقة أن دالة ماركوف العشوائية هي دالة فرعية معيارية)؛
• إن المنفعة الحدية للوكيل لكل عنصر ثنائية (متغيرة) - إما 0 أو 1. أي أن إضافة عنصر إلى حزمة إما لا تضيف أي منفعة، أو تضيف منفعة مقدارها 1.

الحلول التالية معروفة لهذا الإعداد:

• قام بابايوف وإزرا وفيج ^{[ 10 ]} بتصميم آلية حتمية متعددة الحدود وصادقة تُسمى "المساواة ذات الأولوية"، تُخرج تخصيصًا مهيمنًا وفقًا لمعيار لورنز، والذي يكون بالتالي أيضًا EFX _{0 ، ويُعظّم حاصل ضرب المنافع، ويحقق} حصة قصوى بنسبة 1/2 ، ويحقق الحصة القصوى الكاملة عندما تكون التقييمات جمعية. مع الأولويات العشوائية، تكون هذه الآلية خالية من الحسد مسبقًا . كما درسوا التقييمات الثنائية e ، حيث تكون المنفعة الحدية إما غير موجبة أو في النطاق [1، 1 + e ].
• أظهر بينابو، تشاكرابورتي، إيغاراشي، وزيك ^{[ 11 ]} أنه في هذا السياق، يُعظّم كل تخصيص أمثل وفقًا لمبدأ باريتو مجموع المنافع ( الرفاهية النفعية )، وأن مجموعة التخصيصات التي تُعظّم دالة متناظرة مقعرة تمامًا f على جميع تخصيصات المجموع الأقصى لا تعتمد على اختيار f ، وأن جميع هذه التخصيصات التي تُعظّم f هي EF1. وهذا يعني أن تخصيصات الضرب الأقصى هي التخصيصات المثلى وفقًا لمبدأ ليكسيمين ، وأنها جميعًا تُعظّم المجموع الأقصى وEF1. كما قدموا خوارزمية زمنية متعددة الحدود لحساب تخصيص يُعظّم المجموع الأقصى وEF1 (والذي لا يُعظّم بالضرورة دالة مقعرة)، وخوارزمية زمنية متعددة الحدود تُعظّم دالة مقعرة للحالة الخاصة لحقول ماركوف العشوائية القائمة على مطابقة الحد الأقصى للعدد في الرسوم البيانية ثنائية الأجزاء.

تُعد دوال رتبة الماترويد فئة فرعية من تقييمات البدائل الإجمالية .

• أوراكل الرتب