• Home
  • /
  • Blog
  • /
  • شرح مفاهيم 2 الأساسية للرسم البياني للأطفال ميزة

شرح مفاهيم 2 الأساسية للرسم البياني للأطفال ميزة

شرح مفاهيم 2 الأساسية للرسم البياني للأطفال ميزة

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.

مصفوفة التقارب للرسم البياني أعلاه هي

ABCD
A01100110
B1010=1010
C11011101
D00100010
مصفوفة الجوار

في المصفوفة أعلاه ، نظرًا لوجود مسار من A إلى C وكذلك من C إلى A ، فإن إدخال A إلى C و C إلى A هو 1. وينطبق الشيء نفسه على العقد الأخرى.

في حالة توصيل العقدة بنفسها بواسطة حلقة. (العقدة C لها حلقة).

مصفوفة الجوار ومصفوفة المسار
رسم بياني غير موجه مع حلقة
ABCD
A01100110
B1010=1010
C11111111
D00100010
مصفوفة الجوار

مصفوفة الجوار – الرسم البياني الموجه

مصفوفة الجوار ومصفوفة المسار
رسم بياني مباشر مع حلقة

النظر في الرسم البياني الموجه كما هو موضح أعلاه. يوجد مسار من العقدة A إلى العقدة B ، ولكن لا يوجد أي مسار مباشر من العقدة B إلى العقدة A. وبالمثل هناك مسار من العقدة C إلى العقدة A ولكن لا يوجد مثل هذا المسار بين العقدة A إلى العقدة C.

الآن ضع في اعتبارك زوجًا من العقد B و C. يوجد مسار مباشر من العقدة B إلى العقدة C وكذلك من العقدة C إلى العقدة B. المصفوفة المجاورة للرسم البياني أعلاه ممثلة على أنها

ABCD
A01000100
B0010=0010
C11111111
D00000000

مصفوفة المسار

تأمل الرسم البياني التالي

مصفوفة الجوار ومصفوفة المسار
مخطط موجه

مصفوفة التقارب للرسم البياني أعلاه هي

ABCDE
A0101001010
B00100=00100
C0000100001
D0100001000
E0001000010

إذا أخذنا في الاعتبار زوج العقد B و E. من مصفوفة الجوار أعلاه ، نجد أنه لا يوجد مسار مباشر بين B و E. ولكن يوجد مسار من B و E عبر C. يُعرف هذا المسار باسم المسار بطول 2. وبالمثل ، فإن المسار الذي يبلغ طوله 3 سيكون له عقدتان وسيطتان. بشكل عام ، مسار الطول n سيكون له (ن – 1) عقد وسيطة.

للحصول على مصفوفة مسار بطول 2 ، تُضربالمصفوفة المجاورة في نفسها.

010100101001100
001000010000001
0000100001=00010
010000100000100
000100001001000

من المصفوفة أعلاه ، نجد أن هناك مسارًا بطول 2 بين A إلى B ، ومن E إلى B ، ومن A إلى C ، ومن D إلى C ، ومن C إلى D ، ومن B إلى E.

مرة أخرى ، يؤدي ضرب مصفوفة المسار ذات الطول 2 في مصفوفة المجاورة إلى مصفوفة مسار بطول 3.

011000101000101
000010010000010
0001000001=01000
001000100000001
010000001000100

من المصفوفة أعلاه ، نجد أن هناك مسارًا بطول 3 بين C إلى B ، ومن A إلى C ، ومن E إلى C ، ومن B إلى D ، ومن A إلى E ، ومن D إلى E.

بشكل عام ، لإنشاء مصفوفة مسار الطول n ، خذ مصفوفة مسار الطول (n – 1) ، واضربها بمصفوفة مسار طوله 1.

{"email":"Email address invalid","url":"Website address invalid","required":"Required field missing"}
>