انتقل إلى المحتوى

مصفوفة تجاور

من ويكيبيديا، الموسوعة الحرة

في نظرية المخططات وعلوم الكمبيوتر، مصفوفة التجاور[1][2] أو المجاورة (بالإنجليزية: Adjacency Matrix)‏ هي مصفوفة مربعة تستخدم لتمثيل الرسم البياني. عناصر المصفوفة تعكس ما إذا كانت رؤوس الرسم البياني (vertices) متجاورة ومرتبطة أم لا.

أمثلة

[عدل]

الرسوم ومصفوفات المجاورة المقابلة المبينة هنا تشير بأن كل ضلع يربط نقطتين يضيف العدد "1" وكل حلقة داخلية تُضيف "2" آخر. هذا يسمح بمعرفة درجة ارتباط كل نقطة مع النقاط الأخرى عبر أخذ مجموع ارتباطات كل نقطة بغيرها أو مع نفسها (حلقة). فمثلا العنصر الأول في المصفوفة (1,1)A له القيمة 2 وهي بسبب الحلقة الدائرية على النقطة الأولى والعنصر (1,2)A  له القيمة 1 لارتباط الرأسين <1> و <2> بضلع واحد وفي حالة عدم التجاور يأخذ عنصر المصفوفة القيمة صفر.

رسم بياني محدد مصفوفة المجاورة

عناصر مصفوفة المجاورة ذات البعد 6x6

مخطط ناورو

احدائيات العناصر من 0 إلى 23 حيث النقاط البيضاء تشير لعدم المجاورة (القيمة صفر) وشدة اللون تُشير إلى تزايد الترابط.

مخطط موجه لِكايلي S4

رسم بياني موجه المعروف بمخطط كايلي المتجهي.

تحتوي مصفوفة المجاورة لمخطط رسم بياني كامل على العدد في جميع الخلايا ما عدا الخط على طول قطري حيث لا يوجد سوى الأصفار. إن مصفوفة المجاورة لرسم البياني فارغ هي عبارة  مصفوفة منعدمة أو مصفوفة الصفر.[3][4]

انظر أيضا

[عدل]

المصادر

[عدل]
  1. ^ موفق دعبول؛ خضر الأحمد؛ بشير قابيل؛ مروان البواب (2018)، مسرد معجم مصطلحات الرياضيات: إنكليزي - عربي (بالعربية والإنجليزية)، دمشق: مجمع اللغة العربية بدمشق، ص. 84، QID:Q113390270
  2. ^ موفق دعبول؛ بشير قابيل؛ مروان البواب؛ خضر الأحمد (2018)، معجم مصطلحات الرياضيات (بالعربية والإنجليزية)، دمشق: مجمع اللغة العربية بدمشق، ص. 8، OCLC:1369254291، QID:Q108593221
  3. ^ Biggs (1993), Chapter 2 ("The spectrum of a graph"), pp. 7–13.
  4. ^ Godsil, Chris; Royle, Gordon Algebraic Graph Theory, Springer (2001), ISBN 0-387-95241-1, p.164 نسخة محفوظة 13 أبريل 2019 على موقع واي باك مشين.