المستعرض (التوافقية)

في الرياضيات ، وتحديدًا في التوافقية ، إذا كانت لدينا عائلة من المجموعات ، تُسمى هنا المجموعة C ، فإنّ المقطع العرضي (أو المقطع العرضي ^{[ 1 ] [ 2 ] [ 3 ]} ) هو مجموعة تحتوي على عنصر واحد فقط من كل عنصر من عناصر المجموعة. عندما تكون مجموعات المجموعة C منفصلة، ​​فإنّ كل عنصر من عناصر المقطع العرضي يُقابل عنصرًا واحدًا فقط من عناصر المجموعة C (المجموعة التي ينتمي إليها). أما إذا كانت المجموعات الأصلية غير منفصلة، ​​فهناك احتمالان لتعريف المقطع العرضي:

• يتمثل أحد الاختلافات في وجود تقابل f من المستعرض إلى C بحيث يكون x عنصرًا من f ( x ) لكل x في المستعرض. في هذه الحالة، يُطلق على المستعرض أيضًا اسم نظام الممثلين المتميزين (SDR). ^{[ 4 ] : ​​29}
• أما الطريقة الأخرى، الأقل استخدامًا، فلا تتطلب علاقة تناظرية بين عناصر المستعرض ومجموعات C. في هذه الحالة، لا تكون عناصر نظام الممثلين متميزة بالضرورة. ^{[ 5 ] : 692 [ 6 ] : 322}

في علوم الحاسوب ، يعد حساب المستعرضات مفيدًا في العديد من مجالات التطبيق، حيث غالبًا ما يتم وصف مجموعة المدخلات بأنها رسم بياني فائق .

في نظرية المجموعات ، فإن بديهية الاختيار تعادل القول بأن لكل تجزئة قاطعًا. ^{[ 7 ]}

يُعدّ السؤال الأساسي في دراسة العلاقات التفاضلية المحددة (SDR) هو ما إذا كانت هذه العلاقات موجودة أم لا. تُقدّم نظرية هول للزواج شروطًا ضرورية وكافية لكي يكون لمجموعة منتهية من المجموعات، قد تتداخل بعضها، مُستَطَرة. الشرط هو أنه، لكل عدد صحيح k ، يجب أن يحتوي اتحاد أي مجموعة فرعية من k مجموعة على k عنصرًا فريدًا على الأقل . ^{[ 4 ] : ​​29}

يُقدّم التحسين التالي الذي أجراه إتش جيه رايزر حدودًا دنيا لعدد هذه الشبكات الديناميكية الخاصة. ^{[ 8 ] : 48}

نظرية . لتكن S1 _، S2 _، ... ، Sm مجموعة من المجموعات _بحيث${\displaystyle S_{i_{1}}\cup S_{i_{2}}\cup \dots \cup S_{i_{k}}}$تحتوي على الأقل على k عنصرًا لـ k = 1، 2، ...، m ولجميع التوليفات k {${\displaystyle i_{1},i_{2},\ldots ,i_{k}}$لنفترض أن لدينا مجموعة من الأعداد الصحيحة 1، 2، ...، m، وأن كل مجموعة من هذه المجموعات تحتوي على t عنصرًا على الأقل. إذا كان t ≤ m، فإن المجموعة تحتوي على t  ! عنصرًا على الأقل، وإذا كان t > m، فإن المجموعة تحتوي على t  ! / ( t - m )! عنصرًا على الأقل.

يمكن إنشاء رسم بياني ثنائي الأجزاء ، حيث تمثل الرؤوس على أحد الجانبين المجموعات، وتمثل الرؤوس على الجانب الآخر العناصر، وتربط الحواف كل مجموعة بالعناصر التي تحتويها. عندئذٍ، يكون التقاطع (المُعرَّف بأنه نظام من الممثلين المتميزين ) مكافئًا للمطابقة التامة في هذا الرسم البياني.

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

في نظرية الزمر ، إذا كانت لدينا زمرة جزئية H من زمرة G ، فإن المستعرض الأيمن (أو الأيسر) هو مجموعة تحتوي على عنصر واحد فقط من كل مجموعة مشاركة يمنى (أو يسرى) في H. في هذه الحالة، تكون "المجموعات" (المجموعات المشاركة) منفصلة، ​​أي أن المجموعات المشاركة تشكل تجزئة للزمرة .

كحالة خاصة من المثال السابق، بالنظر إلى حاصل الضرب المباشر للمجموعات${\displaystyle G=H\times K}$، إذن H عبارة عن مستعرض للمجموعات المشاركة لـ K.

بشكل عام، بما أن أي علاقة تكافؤ على مجموعة عشوائية تؤدي إلى تقسيم، فإن اختيار أي ممثل من كل فئة تكافؤ ينتج عنه تقاطع.

يحدث مثال آخر على التقاطع القائم على التقسيم عندما ننظر في علاقة التكافؤ المعروفة باسم نواة (نظرية المجموعات) لدالة ، معرفة لدالة${\displaystyle f}$مع اعتبار المجال X بمثابة تقسيم للمجال${\displaystyle \operatorname {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X\,\right\}}$والتي تقسم مجال f إلى فئات تكافؤ بحيث ترتبط جميع العناصر في الفئة عبر f بنفس القيمة. إذا كانت f أحادية، فلا يوجد سوى تقاطع واحد لـ${\displaystyle \operatorname {ker} f}$بالنسبة لدالة f غير الموجبة بالضرورة ، يتم تثبيت مستعرض T من${\displaystyle \operatorname {ker} f}$يُنشئ هذا تطابقًا واحدًا لواحد بين T وصورة f ، والتي يُشار إليها فيما يلي بـ${\displaystyle \operatorname {Im} f}$وبالتالي، دالة${\displaystyle g:(\operatorname {Im} f)\to T}$يتم تعريفها جيدًا من خلال الخاصية التي تنص على أنه لكل z في${\displaystyle \operatorname {Im} f,g(z)=x}$حيث x هو العنصر الوحيد في T بحيث${\displaystyle f(x)=z}$علاوة على ذلك، يمكن توسيع الدالة g (ليس بالضرورة بطريقة فريدة) بحيث تُعرَّف على كامل المجال المقابل للدالة f عن طريق اختيار قيم عشوائية لـ g(z) عندما تكون z خارج صورة f . ومن السهل حسابيًا التحقق من أن g المُعرَّفة بهذه الطريقة تتمتع بالخاصية التالية:${\displaystyle f\circ g\circ f=f}$، وهو البرهان (عندما يكون مجال ومجال f هو نفس المجموعة) على أن شبه المجموعة التحويلية الكاملة هي شبه مجموعة منتظمة .${\displaystyle g}$يعمل كشبه معكوس (ليس بالضرورة فريدًا) للدالة f ؛ وفي نظرية شبه الزمر، يُطلق عليه ببساطة اسم المعكوس. لاحظ مع ذلك أنه بالنسبة لأي دالة g تتمتع بالخاصية المذكورة أعلاه، فإن المعادلة "الثنائية"${\displaystyle g\circ f\circ g=g}$قد لا يكون هذا صحيحًا. ولكن إذا رمزنا بـ${\displaystyle h=g\circ f\circ g}$إذن، فإن f هي شبه معكوس لـ h ، أي${\displaystyle h\circ f\circ h=h}$.

مقطع عرضي مشترك للمجموعتين A و B (حيث${\displaystyle |A|=|B|=n}$المجموعة A هي مجموعة قاطعة لكل من A و B. للمجموعتين A و B قاطع مشترك إذا وفقط إذا كان لكل${\displaystyle I,J\subset \{1,...,n\}}$،

${\displaystyle |(\bigcup _{i\in I}A_{i})\cap (\bigcup _{j\in J}B_{j})|\geq |I|+|J|-n}$^{[ 9 ]}

المستعرض الجزئي هو مجموعة تحتوي على عنصر واحد على الأكثر من كل عنصر من عناصر المجموعة، أو (بصيغة أدق للمفهوم) مجموعة تحتوي على عنصر تقابلي من المجموعة إلى C. تشكل مستعرضات مجموعة منتهية C من المجموعات المنتهية مجموعات الأساس لماترويد ، وهو الماترويد المستعرض لـ C. المجموعات المستقلة في الماترويد المستعرض هي المستعرضات الجزئية لـ C. ^{[ 10 ]}

المستعرض المستقل (ويُسمى أيضًا مجموعة قوس قزح المستقلة أو نظام الممثلين المستقل ) هو مستعرض يُمثل أيضًا مجموعة مستقلة في رسم بياني مُعطى. ولتوضيح الفرق بشكل مجازي، لنفترض كليةً تضم m قسمًا، حيث يرغب عميد الكلية في تشكيل لجنة من m عضو، عضو واحد لكل قسم. هذه اللجنة هي مستعرض. ولكن الآن، لنفترض أن بعض أعضاء هيئة التدريس لا يُحبون بعضهم البعض ولا يتفقون على الجلوس معًا في اللجنة. في هذه الحالة، يجب أن تكون اللجنة مستعرضًا مستقلًا، حيث يصف الرسم البياني الأساسي علاقات "عدم الإعجاب". ^{[ 11 ]}

يُمكن تعميم مفهوم المستعرض من خلال تعريف مجموعة تتقاطع مع كل عنصر من عناصر المجموعة C تقاطعًا غير فارغ . ومن أمثلة هذه المجموعة مجموعة برنشتاين ، التي تُعرَّف بأنها مجموعة تتقاطع مع كل مجموعة من عناصر C تقاطعًا غير فارغ ، ولكنها لا تحتوي على أي مجموعة من عناصر C ، حيث C هي مجموعة جميع المجموعات الكاملة في فضاء بولندي طوبولوجي . كمثال آخر، إذا كانت C تتكون من جميع خطوط مستوى إسقاطي ، فإن مجموعة الحجب في هذا المستوى هي مجموعة من النقاط التي تتقاطع مع كل خط ولكنها لا تحتوي على أي خط.

في لغة نظرية الفئات ، فإن المقطع العرضي لمجموعة من المجموعات المنفصلة بشكل متبادل هو مقطع من خريطة القسمة الناتجة عن المجموعة.

تمت دراسة التعقيد الحسابي لحساب جميع المستعرضات لمجموعة إدخال من المجموعات ، وخاصة في إطار خوارزميات التعداد .

• بديهية الاختيار
• دائم

• لولر، إي إل. التحسين التوافقي: الشبكات والمصفوفات. 1976.
• ميرسكي، ليون (1971). نظرية التقاطع: عرض لبعض جوانب الرياضيات التوافقية. دار النشر الأكاديمية. ISBN 0-12-498550-5.