ما هي مصفوفة الجوار؟
في هذه المقالة، سنناقش مصفوفة الجوار مع تمثيلها.
تعريف مصفوفة المجاورة
في نظرية الرسم البياني، مصفوفة الجوار هي طريقة كثيفة لوصف بنية الرسم البياني المحدود. إنها مصفوفة ثنائية الأبعاد تُستخدم لتعيين الارتباط بين عقد الرسم البياني.
إذا كان الرسم البياني لديه ن عدد القمم، ثم مصفوفة الجوار لهذا الرسم البياني ن × ن ، وكل إدخال في المصفوفة يمثل عدد الحواف من قمة إلى أخرى.
تسمى مصفوفة الجوار أيضًا باسم مصفوفة الاتصال . في بعض الأحيان يطلق عليه أيضًا أ مصفوفة قمة الرأس .
تمثيل مصفوفة المجاورة
إذا كان الرسم البياني غير الموجه G يتكون من رؤوس n، فإن مصفوفة الجوار للرسم البياني هي n x n مصفوفة A = [aij] ويتم تحديدها بواسطة -
أ اي جاي = 1 {إذا كان هناك مسار موجود من V أنا إلى V ي }
أ اي جاي = 0 {خلاف ذلك}
دعونا نرى بعض النقاط المهمة فيما يتعلق بمصفوفة الجوار.
- إذا كانت هناك حافة بين الرأس V أنا و V ي ، حيث i عبارة عن صف، وj عمود، ثم قيمة a اي جاي = 1.
- إذا لم يكن هناك حافة بين قمة V أنا و V ي ، ثم قيمة أ اي جاي = 0.
- إذا لم تكن هناك حلقات ذاتية في الرسم البياني البسيط، فيجب أن تحتوي المصفوفة الرأسية (أو المصفوفة المجاورة) على 0s في القطر.
- تكون المصفوفة المجاورة متماثلة بالنسبة للرسم البياني غير الموجه. ويحدد أن القيمة في i ذ صف و ي ذ العمود يساوي القيمة في j ذ الصف الأول ذ
- إذا كانت المصفوفة المجاورة مضروبة في نفسها، وإذا كانت هناك قيمة غير الصفر موجودة في i ذ صف و ي ذ العمود، ثم هناك الطريق من V أنا إلى V ي بطول يعادل 2. تمثل القيمة غير الصفرية في مصفوفة الجوار وجود عدد من المسارات المميزة.
ملاحظة: في مصفوفة الجوار، يمثل 0 أنه لا يوجد ارتباط بين عقدتين، بينما يمثل 1 أنه يوجد ارتباط بين عقدتين.
كيفية إنشاء مصفوفة المجاورة؟
لنفترض أن هناك رسما بيانيا ز مع ن عدد القمم، ثم يتم إعطاء مصفوفة الرأس (أو مصفوفة المجاورة) بواسطة -
أ = أ أحد عشر أ 12 . . . . . أ 1 ن أ واحد وعشرين أ 22 . . . . . أ 2n . . . . . . . . . أ ن1 أ n2 . . . . . أ ن.ن
حيث أ اي جاي يساوي عدد الحواف من الرأس i إلى j. كما ذكر أعلاه، تكون مصفوفة المجاورة متماثلة بالنسبة للرسم البياني غير الموجه، لذلك بالنسبة للرسم البياني غير الموجه، اي جاي = أ هه .
عندما تكون الرسوم البيانية بسيطة ولا توجد أوزان على الحواف أو حواف متعددة، فإن إدخالات مصفوفة الجوار ستكون 0 و 1. إذا لم تكن هناك حلقات ذاتية، فإن الإدخالات القطرية لمصفوفة الجوار ستكون 0.
الآن، دعونا نرى مصفوفة المجاورة للرسم البياني غير الموجه وللرسوم البيانية الموجهة.
مصفوفة المجاورة للرسم البياني غير الموجه
في الرسم البياني غير الموجه، لا ترتبط الحواف بالاتجاهات الموجودة بها. في الرسم البياني غير الموجه، إذا كانت هناك حافة بين Vertex A وVertex B، فيمكن نقل القمم من A إلى B وكذلك من B إلى A.
دعونا نفكر في الرسم البياني غير الموجه أدناه ونحاول بناء مصفوفة المجاورة له.
في الرسم البياني، يمكننا أن نرى عدم وجود حلقة ذاتية، وبالتالي فإن الإدخالات القطرية للمصفوفة المجاورة ستكون 0. وستكون مصفوفة الجوار في الرسم البياني أعلاه -
مصفوفة المجاورة للرسم البياني الموجه
في الرسم البياني الموجه، تشكل الحواف زوجًا مرتبًا. تمثل الحواف مسارًا محددًا من قمة A إلى قمة أخرى B. وتسمى العقدة A بالعقدة الأولية، بينما تسمى العقدة B بالعقدة الطرفية.
دعونا نفكر في الرسم البياني الموجه أدناه ونحاول بناء مصفوفة المجاورة له.
في الرسم البياني أعلاه، يمكننا أن نرى عدم وجود حلقة ذاتية، وبالتالي فإن الإدخالات القطرية للمصفوفة المجاورة ستكون 0. وستكون مصفوفة الجوار في الرسم البياني أعلاه -
خصائص مصفوفة المجاورة
يتم سرد بعض خصائص مصفوفة المجاورة على النحو التالي:
- مصفوفة الجوار هي مصفوفة تحتوي على صفوف وأعمدة تستخدم لتمثيل رسم بياني بسيط مسمى بالأرقام 0 و1 في موضع (V أنا ، في ي )، وفقا لشرط وجود V2 أم لا أنا و V ي متجاورة.
- بالنسبة للرسم البياني الموجه، إذا كانت هناك حافة موجودة بين الرأس i أو V أنا إلى Vertex j أو V ي ، ثم قيمة A[V أنا ][في ي ] = 1، وإلا ستكون القيمة 0.
- بالنسبة للرسم البياني غير الموجه، إذا كانت هناك حافة موجودة بين الرأس i أو V أنا إلى Vertex j أو V ي ، ثم قيمة A[V أنا ][في ي ] = 1 و أ[V ي ][في أنا ] = 1، وإلا ستكون القيمة 0.
دعونا نرى بعض الأسئلة حول مصفوفة الجوار. الأسئلة أدناه تتعلق بالرسوم البيانية الموزونة وغير الموجهة.
ملاحظة: يُقال أن الرسم البياني هو الرسم البياني الموزون إذا تم تعيين رقم موجب لكل حافة، وهو ما يسمى وزن الحافة.
السؤال رقم 1 - ماذا ستكون مصفوفة الجوار للرسم البياني المرجح غير الموجه أدناه؟
حل - في السؤال المطروح، لا توجد حلقة ذاتية، لذلك من الواضح أن الإدخالات القطرية للمصفوفة المجاورة للرسم البياني أعلاه ستكون 0. الرسم البياني أعلاه هو رسم بياني مرجح غير موجه. سيتم تمثيل الأوزان الموجودة على حواف الرسم البياني كمدخلات لمصفوفة الجوار.
مصفوفة الجوار للرسم البياني أعلاه ستكون -
السؤال 2 - ماذا ستكون مصفوفة الجوار للرسم البياني المرجح الموجه أدناه؟
حل - في السؤال المطروح، لا توجد حلقة ذاتية، لذلك من الواضح أن الإدخالات القطرية للمصفوفة المجاورة للرسم البياني أعلاه ستكون 0. الرسم البياني أعلاه هو رسم بياني موجه مرجح. سيتم تمثيل الأوزان الموجودة على حواف الرسم البياني كمدخلات لمصفوفة الجوار.
مصفوفة الجوار للرسم البياني أعلاه ستكون -
نأمل أن تكون هذه المقالة مفيدة لك لفهم مصفوفة الجوار. لقد ناقشنا هنا مصفوفة الجوار بالإضافة إلى إنشائها وخصائصها. لقد ناقشنا أيضًا تكوين مصفوفة المجاورة على الرسوم البيانية الموجهة أو غير الموجهة، سواء كانت مرجحة أم لا.
