مصفوفة التجاور

يمكن كتابة مصفوفة التجاور A للرسم البياني ثنائي الأجزاء الذي يحتوي جزآه على r و s من الرؤوس على الصورة التالية:

${\displaystyle A={\begin{pmatrix}0_{r,r}&B\\B^{\mathsf {T}}&0_{s,s}\end{pmatrix}},}$

حيث B مصفوفة من الرتبة r × s ، و 0 _{r و} 0 _s و _s تمثلان المصفوفتين الصفريتين من الرتبة r × r و s × s _{على التوالي} . في هذه الحالة، تمثل المصفوفة B الأصغر الرسم البياني بشكل فريد، ويمكن تجاهل الأجزاء المتبقية من A باعتبارها زائدة. تُسمى B أحيانًا مصفوفة التجاور الثنائي .

بصورة رسمية، ليكن G = ( _U , V , E ) رسمًا بيانيًا ثنائي الأجزاء يتكون من الأجزاء U = { u1 _, ..., ur } و V = { v1 _, ..., vs } والحواف E. مصفوفة التجاور الثنائي هي المصفوفة B من الرتبة r × s التي تحتوي على 0-1، _حيث يكون b_{_{i , j}} = 1 إذا وفقط إذا كان ( u _{_i , vj} ) ∈ E.

إذا كان G عبارة عن رسم بياني متعدد الأجزاء ثنائي الأجزاء أو رسم بياني مرجح ، فإن العناصر b _i,j تعتبر على التوالي عدد الحواف بين الرؤوس أو وزن الحافة ( u _i , v _j ) .

مصفوفة التجاور A من النوع ( a , b , c ) للرسم البياني البسيط تحتوي على A_{_{i , j}} = a إذا كان ( i , j ) ضلعًا، و b إذا لم يكن كذلك، و c على القطر الرئيسي. مصفوفة التجاور لسيدل هي مصفوفة تجاور من النوع (−1, 1, 0) . تُستخدم هذه المصفوفة في دراسة الرسوم البيانية المنتظمة بقوة والرسوم البيانية الثنائية . ^{[ 3 ]}

تحتوي مصفوفة المسافة في الموضع ( i , j ) على المسافة بين الرأسين v_{_i} و v_{_j}. المسافة هي طول أقصر مسار يربط بين الرأسين. ما لم تُحدد أطوال الحواف صراحةً، فإن طول المسار هو عدد الحواف فيه. تشبه مصفوفة المسافة مصفوفة التجاور ذات القوة العالية، ولكن بدلاً من تحديد ما إذا كان رأسان متصلين أم لا (أي مصفوفة الاتصال التي تحتوي على قيم منطقية )، فإنها تُعطي المسافة الدقيقة بينهما.

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

رسم بياني مُصنَّف	مصفوفة التجاور
	${\displaystyle {\begin{pmatrix}2&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{pmatrix}}}$ الإحداثيات من 1 إلى 6.
رسم بياني لناورو	تتراوح الإحداثيات من 0 إلى 23. الحقول البيضاء تمثل أصفارًا، والحقول الملونة تمثل واحدًا.

يمكن أن تكون مصفوفة التجاور للرسم البياني الموجه غير متناظرة. ويمكن تعريف مصفوفة التجاور للرسم البياني الموجه إما بحيث

1. يشير العنصر غير الصفري A _ij إلى وجود حافة من i إلى j أو
2. يشير ذلك إلى وجود حافة من j إلى i .

يُستخدم التعريف الأول عادةً في نظرية الرسوم البيانية وتحليل الشبكات الاجتماعية (مثل علم الاجتماع، والعلوم السياسية، والاقتصاد، وعلم النفس). ^{[ 5 ]} أما التعريف الثاني فهو أكثر شيوعًا في العلوم التطبيقية الأخرى (مثل الأنظمة الديناميكية، والفيزياء، وعلم الشبكات) حيث يُستخدم A أحيانًا لوصف الديناميكيات الخطية على الرسوم البيانية. ^{[ 6 ]}

باستخدام التعريف الأول، يمكن حساب درجات الدخول لرأس ما بجمع قيم العمود المقابل، ودرجات الخروج بجمع قيم الصف المقابل. أما باستخدام التعريف الثاني، فتُحسب درجة الدخول بجمع قيم الصف المقابل، ودرجات الخروج بجمع قيم العمود المقابل.

رسم بياني مُصنَّف	مصفوفة التجاور
الرسم البياني الموجه لكايلي لـ S 4	تتراوح الإحداثيات بين 0 و23. وبما أن الرسم البياني موجه، فإن المصفوفة ليست بالضرورة متناظرة .

تحتوي مصفوفة التجاور للرسم البياني الكامل على جميع القيم 1 باستثناء القطر الرئيسي حيث توجد جميع القيم 0. أما مصفوفة التجاور للرسم البياني الفارغ فهي مصفوفة صفرية .

مصفوفة التجاور للرسم البياني البسيط غير الموجه متناظرة ، وبالتالي لها مجموعة كاملة من القيم الذاتية الحقيقية وقاعدة متجهات ذاتية متعامدة . مجموعة القيم الذاتية للرسم البياني هي طيف الرسم البياني. ^{[ 7 ]} من الشائع الإشارة إلى القيم الذاتية بـ${\displaystyle \lambda _{1}\geq \lambda _{2}\geq \cdots \geq \lambda _{n}.}$

أكبر قيمة ذاتية${\displaystyle \lambda _{1}}$تكون محدودة من الأعلى بالدرجة القصوى. يمكن اعتبار هذا نتيجة لنظرية بيرون-فروبينيوس ، ولكن يمكن إثباته بسهولة. ليكن v متجهًا ذاتيًا واحدًا مرتبطًا بـ${\displaystyle \lambda _{1}}$و x عنصرًا تكون فيه قيمة v المطلقة هي القيمة القصوى. وبدون فقدان للعمومية، نفترض أن v _x موجب، لأنه بخلاف ذلك، نأخذ ببساطة المتجه الذاتي − v ، المرتبط أيضًا بـ${\displaystyle \lambda _{1}}$. ثم

${\displaystyle \lambda _{1}v_{x}=(Av)_{x}=\sum _{y=1}^{n}A_{x,y}v_{y}\leq \sum _{y=1}^{n}A_{x,y}v_{x}=v_{x}\deg(x).}$

بالنسبة للرسوم البيانية المنتظمة من الدرجة d ، فإن d هي القيمة الذاتية الأولى للمصفوفة A للمتجه v = (1, ..., 1) (من السهل التحقق من أنها قيمة ذاتية وأنها القيمة القصوى نظرًا للحد المذكور أعلاه). تعدد هذه القيمة الذاتية هو عدد المكونات المتصلة في G ، على وجه الخصوص${\displaystyle \lambda _{1}>\lambda _{2}}$بالنسبة للرسوم البيانية المتصلة. يمكن إثبات أنه لكل قيمة ذاتية${\displaystyle \lambda _{i}}$عكسه${\displaystyle -\lambda _{i}=\lambda _{n+1-i}}$كما أنها قيمة ذاتية لـ A إذا كان G رسمًا بيانيًا ثنائي الأجزاء . ^{[ 8 ]} على وجه الخصوص، فإن −d هي قيمة ذاتية لأي رسم بياني ثنائي الأجزاء منتظم من الدرجة d .

الفرق${\displaystyle \lambda _{1}-\lambda _{2}}$يُطلق عليه اسم الفجوة الطيفية ، وهو مرتبط بتوسع G. ومن المفيد أيضًا تعريف نصف القطر الطيفي لـ${\displaystyle A}$يرمز إليه بـ${\displaystyle \lambda (G)=\max _{\left|\lambda _{i}\right|<d}|\lambda _{i}|}$هذا العدد محدود بـ${\displaystyle \lambda (G)\geq 2{\sqrt {d-1}}-o(1)}$هذا الحد ضيق في رسوم رامانوجان البيانية .

_{لنفترض وجود} رسمين بيانيين موجهين أو غير موجهين _G1 و _G2 مع مصفوفات تجاور A1 _{و A2} . يكون G1 و G2 متماثلين إذا وفقط إذا وُجدت مصفوفة تبديل _P بحيث

${\displaystyle PA_{1}P^{-1}=A_{2}.}$

على وجه الخصوص، يتشابه الرسمان البيانيان _A1 و A2 ، _{وبالتالي} يمتلكان نفس متعددة الحدود الدنيا ، ومتعددة الحدود المميزة ، والقيم الذاتية ، والمحدد ، والأثر . لذا، يمكن اعتبار هذه العناصر ثوابت تماثلية للرسوم البيانية. مع ذلك، قد يمتلك رسمان بيانيان نفس مجموعة القيم الذاتية دون أن يكونا متماثلين. ^{[ 9 ]} يُقال إن هذه المؤثرات الخطية متساوية الطيف .

إذا كانت A هي مصفوفة التجاور للرسم البياني الموجه أو غير الموجه G ، فإن المصفوفة A n (أي حاصل ضرب n نسخة من A ) لها تفسير مثير للاهتمام: يُعطي العنصر ( i , j ) عدد المسارات (الموجهة أو غير الموجهة) التي طولها n من الرأس i إلى الرأس j . [ 10 ] إذا كان n أصغر عدد صحيح غير سالب، بحيث يكون العنصر ( i , j ) من A  n  موجبًا لبعض i و j ، فإن n n  هو المسافة بين الرأس i والرأس j . ومن الأمثلة الرائعة على فائدة ذلك حساب عدد المثلثات في الرسم البياني غير الموجه G ، وهو بالضبط أثر A 3  مقسومًا على 3 أو 6 اعتمادًا على ما إذا كان الرسم البياني موجهًا أم لا. نقسم على هذه القيم للتعويض عن التكرار في حساب كل مثلث. في الرسم البياني غير الموجه، يُحتسب كل مثلث مرتين لجميع العقد الثلاث، لأن المسار يمكن اتباعه باتجاه عقارب الساعة أو عكسها : ijk أو ikj. ويمكن استخدام مصفوفة التجاور لتحديد ما إذا كان الرسم البياني متصلاً أم لا . 

إذا كان للرسم البياني الموجه مصفوفة تجاور معدومة (أي، إذا كان هناك عدد n بحيث تكون A ⁿ هي المصفوفة الصفرية)، فإنه يكون رسمًا بيانيًا موجهًا غير دوري . ^{[ 11 ]}