مصفوفة الحدوث

في نظرية الرسم البياني، يحتوي الرسم البياني غير الموجه على نوعين من مصفوفات الوقوع: غير الموجهة والموجهة.

مصفوفة الحدوث غير الموجهة (أو ببساطة مصفوفة الحدوث ) للرسم البياني غير الموجه هي${\displaystyle n\times m}$المصفوفة B ، حيث n و m هما عدد الرؤوس والحواف على التوالي، بحيث

${\displaystyle B_{ij}={\begin{cases}1&{\text{إذا كان الرأس }}v_{i}{\text{ متصلاً بالحافة }}e_{j},\\0&{\text{فيما عدا ذلك.}}\end{cases}}}$

على سبيل المثال، مصفوفة الوقوع للرسم البياني غير الموجه الموضح على اليمين هي مصفوفة تتكون من 4 صفوف (تتوافق مع الرؤوس الأربعة، من 1 إلى 4) و4 أعمدة (تتوافق مع الحواف الأربعة،${\displaystyle e_{1},e_{2},e_{3},e_{4}}$):

إذا نظرنا إلى مصفوفة الوقوع، فسنجد أن مجموع كل عمود يساوي 2. وذلك لأن كل حافة لها رأس متصل بكل طرف.

مصفوفة الوقوع للرسم البياني الموجه هي${\displaystyle n\times m}$المصفوفة B حيث n و m هما عدد الرؤوس والحواف على التوالي، بحيث

${\displaystyle B_{ij}={\begin{cases}{-1}&{\text{إذا غادرت الحافة }}e_{j}{\text{ الرأس }}v_{i},\\{\phantom {-}}1&{\text{إذا دخلت الحافة }}e_{j}{\text{ الرأس }}v_{i},\\{\phantom {-}}0&{\text{فيما عدا ذلك.}}\end{cases}}}$

(يستخدم العديد من المؤلفين اصطلاح الإشارة المعاكس.)

مصفوفة الوقوع الموجهة للرسم البياني غير الموجه هي مصفوفة الوقوع، بمعنى الرسوم البيانية الموجهة، لأي اتجاه للرسم البياني. أي أنه في عمود الحافة e ، يوجد 1 واحد في الصف المقابل لأحد رؤوس e و-1 واحد في الصف المقابل للرأس الآخر من e ، وجميع الصفوف الأخرى تحتوي على 0. مصفوفة الوقوع الموجهة فريدة من نوعها حتى نفي أي من أعمدتها، لأن نفي عناصر عمود ما يقابله عكس اتجاه الحافة.

ترتبط مصفوفة الوقوع غير الموجهة للرسم البياني G بمصفوفة التجاور للرسم البياني الخطي L ( G ) من خلال النظرية التالية:

${\displaystyle A(L(G))=B(G)^{\textsf {T}}B(G)-2I_{m}.}$

حيث A ( L ( G )) هي مصفوفة التجاور للرسم البياني الخطي لـ G ، و B ( G ) هي مصفوفة الوقوع ، و I _m هي مصفوفة الوحدة ذات البعد m .

يتم الحصول على مصفوفة لابلاس المنفصلة (أو مصفوفة كيرشوف) من مصفوفة الوقوع الموجهة B ( G ) بواسطة الصيغة التالية

${\displaystyle B(G)B(G)^{\textsf {T}}.}$

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

مصفوفة الوقوع للرسم البياني الموقّع هي تعميم لمصفوفة الوقوع الموجّهة. وهي مصفوفة الوقوع لأي رسم بياني ثنائي الاتجاه يوجّه الرسم البياني الموقّع المعطى. يحتوي عمود الحافة الموجبة على 1 في الصف المقابل لإحدى نقطتي البداية و-1 في الصف المقابل لنقطة البداية الأخرى، تمامًا كما هو الحال في الحافة في الرسم البياني العادي (غير الموقّع). أما عمود الحافة السالبة فيحتوي إما على 1 أو -1 في كلا الصفين. وتُعمّم خصائص الرسم البياني الخطي ومصفوفة كيرشوف على الرسوم البيانية الموقّعة.

تنطبق تعريفات مصفوفة الوقوع على الرسوم البيانية ذات الحلقات والحواف المتعددة . يكون عمود مصفوفة الوقوع الموجهة الذي يتوافق مع حلقة ما أصفارًا بالكامل، إلا إذا كان الرسم البياني موجب الإشارة وكانت الحلقة سالبة؛ فحينها يكون العمود أصفارًا بالكامل باستثناء ±2 في صف رأس الوقوع.

يمكن تمثيل الرسم البياني الموزون باستخدام وزن الحافة بدلاً من الرقم 1. على سبيل المثال، مصفوفة الوقوع للرسم البياني الموجود على اليمين هي:

بما أن حواف الرسوم البيانية العادية لا يمكن أن تحتوي إلا على رأسين (رأس في كل طرف)، فإن عمود مصفوفة الوقوع للرسوم البيانية لا يمكن أن يحتوي إلا على عنصرين غير صفريين. في المقابل، يمكن أن يحتوي الرسم البياني الفائق على عدة رؤوس مرتبطة بحافة واحدة؛ لذا، فإن مصفوفة عامة من الأعداد الصحيحة غير السالبة تصف الرسم البياني الفائق.

من الأمثلة المهمة الهندسة المحدودة . ففي المستوى المحدود، على سبيل المثال، X هي مجموعة النقاط و Y هي مجموعة الخطوط. أما في الهندسة المحدودة ذات الأبعاد الأعلى، فقد تكون X هي مجموعة النقاط و Y هي مجموعة الفضاءات الجزئية ذات البعد الأقل بواحد من بُعد الفضاء الكلي (المستويات الفائقة)؛ أو بشكل أعم، قد تكون X هي مجموعة جميع الفضاءات الجزئية ذات البعد d و Y هي مجموعة جميع الفضاءات الجزئية ذات البعد e ، مع تعريف التداخل على أنه احتواء.

وبالمثل، يمكن تمثيل العلاقة بين الخلايا التي تختلف أبعادها بمقدار واحد في متعدد السطوح بواسطة مصفوفة وقوع. ^{[ 1 ]}

مثال آخر هو تصميم الكتل . هنا، X هي مجموعة منتهية من "النقاط"، و Y هي فئة من المجموعات الجزئية من X ، تُسمى "الكتل"، وتخضع لقواعد تعتمد على نوع التصميم. تُعد مصفوفة الوقوع أداة مهمة في نظرية تصميمات الكتل. على سبيل المثال، يمكن استخدامها لإثبات متباينة فيشر ، وهي نظرية أساسية في تصميمات 2-غير المكتملة المتوازنة (BIBDs)، والتي تنص على أن عدد الكتل لا يقل عن عدد النقاط. ^{[ 2 ]} وباعتبار الكتل نظامًا من المجموعات، فإن الثابت في مصفوفة الوقوع هو عدد أنظمة الممثلين المتميزين (SDRs).