This post is also available in: English (الإنجليزية) हिन्दी (الهندية)
يمكن تمثيل الرسم البياني الذي يحتوي على عدد n من العقد في شكل مصفوفة مربعة من الرتبة n. في هذه المقالة ، نقدم مفهومين أساسيين للرسم البياني الموضح لميزة الأطفال. هذه هي مصفوفة الجوار ومصفوفة المسار.
مصفوفة الجوار ومصفوفة المسار
تتكون الشبكة عادة من مئات أو آلاف العقد المتصلة ببعضها البعض عن طريق الحواف. يمكن تمثيل هذه الشبكات على شكل رسوم بيانية، وهو نوع من بنية البيانات. هل تساءلت يومًا كيف يتم إنشاء مسار بين عقدتين لتسهيل الاتصال غير المنقطع؟
لفهم هذا ، يجب أن يعرف المرء مفهومين أساسيين للرسوم البيانية
- مصفوفة الجوار
- مصفوفة المسار
مصفوفة الجوار
في نظرية الرسم البياني وعلوم الكمبيوتر ، المصفوفة المجاورة هي مصفوفة مربعة تستخدم لتمثيل رسم بياني محدود. تشير عناصر المصفوفة إلى ما إذا كانت أزواج الرؤوس متجاورة أم لا في الرسم البياني.
عناصر مصفوفة التقارب إما 0 أو 1. إذا كان زوج من العقد له حافة مشتركة (على سبيل المثال ، العقد متصلة) ، يتم تمثيلها بواسطة 1. إذا كان زوج من العقد لا يحتوي على حافة مشتركة (على سبيل المثال ، العقد غير متصلة) ، يتم تمثيلها بواسطة 0.
دعونا نفهم الآن كيف يتم تمثيل الرسوم البيانية غير الموجهة والموجهة بواسطة مصفوفة مجاورة.
مصفوفة الجوار – رسم بياني غير موجه
في هذا الرسم البياني ، تكون العقدة A مجاورة للعقدتين B و C. وبالمثل ، تكون العقدة B مجاورة للعقدتين A و C ؛ العقدة C مجاورة للعقد A و B و D ؛ العقدة D مجاورة للعقدة C.
مصفوفة التقارب للرسم البياني أعلاه هي
| A | B | C | D | ||||||
| A | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |
| B | 1 | 0 | 1 | 0 | = | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | |
| D | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
في المصفوفة أعلاه ، نظرًا لوجود مسار من A إلى C وكذلك من C إلى A ، فإن إدخال A إلى C و C إلى A هو 1. وينطبق الشيء نفسه على العقد الأخرى.
في حالة توصيل العقدة بنفسها بواسطة حلقة. (العقدة C لها حلقة).
| A | B | C | D | ||||||
| A | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | |
| B | 1 | 0 | 1 | 0 | = | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| D | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
مصفوفة الجوار – الرسم البياني الموجه
النظر في الرسم البياني الموجه كما هو موضح أعلاه. يوجد مسار من العقدة A إلى العقدة B ، ولكن لا يوجد أي مسار مباشر من العقدة B إلى العقدة A. وبالمثل هناك مسار من العقدة C إلى العقدة A ولكن لا يوجد مثل هذا المسار بين العقدة A إلى العقدة C.
الآن ضع في اعتبارك زوجًا من العقد B و C. يوجد مسار مباشر من العقدة B إلى العقدة C وكذلك من العقدة C إلى العقدة B. المصفوفة المجاورة للرسم البياني أعلاه ممثلة على أنها
| A | B | C | D | ||||||
| A | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | |
| B | 0 | 0 | 1 | 0 | = | 0 | 0 | 1 | 0 |
| C | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
مصفوفة المسار
تأمل الرسم البياني التالي
مصفوفة التقارب للرسم البياني أعلاه هي
| A | B | C | D | E | |||||||
| A | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | |
| B | 0 | 0 | 1 | 0 | 0 | = | 0 | 0 | 1 | 0 | 0 |
| C | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | |
| D | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |
| E | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
إذا أخذنا في الاعتبار زوج العقد B و E. من مصفوفة الجوار أعلاه ، نجد أنه لا يوجد مسار مباشر بين B و E. ولكن يوجد مسار من B و E عبر C. يُعرف هذا المسار باسم المسار بطول 2. وبالمثل ، فإن المسار الذي يبلغ طوله 3 سيكون له عقدتان وسيطتان. بشكل عام ، مسار الطول n سيكون له (ن – 1) عقد وسيطة.
للحصول على مصفوفة مسار بطول 2 ، تُضربالمصفوفة المجاورة في نفسها.
| 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | ||
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | ||
| 0 | 0 | 0 | 0 | 1 | ✕ | 0 | 0 | 0 | 0 | 1 | = | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | ||
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
من المصفوفة أعلاه ، نجد أن هناك مسارًا بطول 2 بين A إلى B ، ومن E إلى B ، ومن A إلى C ، ومن D إلى C ، ومن C إلى D ، ومن B إلى E.
مرة أخرى ، يؤدي ضرب مصفوفة المسار ذات الطول 2 في مصفوفة المجاورة إلى مصفوفة مسار بطول 3.
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | ||
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | ||
| 0 | 0 | 0 | 1 | 0 | ✕ | 0 | 0 | 0 | 0 | 1 | = | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | ||
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
من المصفوفة أعلاه ، نجد أن هناك مسارًا بطول 3 بين C إلى B ، ومن A إلى C ، ومن E إلى C ، ومن B إلى D ، ومن A إلى E ، ومن D إلى E.
بشكل عام ، لإنشاء مصفوفة مسار الطول n ، خذ مصفوفة مسار الطول (n – 1) ، واضربها بمصفوفة مسار طوله 1.
