في هذه المقالة، سنناقش مصفوفة الجوار مع تمثيلها.
إدراج الخلية في
تعريف مصفوفة المجاورة
في نظرية الرسم البياني، مصفوفة الجوار هي طريقة كثيفة لوصف بنية الرسم البياني المحدود. إنها مصفوفة ثنائية الأبعاد تُستخدم لتعيين الارتباط بين عقد الرسم البياني.
إذا كان الرسم البياني لديه ن عدد القمم، ثم مصفوفة الجوار لهذا الرسم البياني ن × ن ، وكل إدخال في المصفوفة يمثل عدد الحواف من قمة إلى أخرى.
تسمى مصفوفة الجوار أيضًا باسم مصفوفة الاتصال . في بعض الأحيان يطلق عليه أيضًا أ مصفوفة قمة الرأس .
تمثيل مصفوفة المجاورة
إذا كان الرسم البياني غير الموجه 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 بالعقدة الطرفية.
إزالة الحرف الأول من Excel
دعونا نفكر في الرسم البياني الموجه أدناه ونحاول بناء مصفوفة المجاورة له.
في الرسم البياني أعلاه، يمكننا أن نرى عدم وجود حلقة ذاتية، وبالتالي فإن الإدخالات القطرية للمصفوفة المجاورة ستكون 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 - ماذا ستكون مصفوفة الجوار للرسم البياني المرجح غير الموجه أدناه؟
hasnext java
حل - في السؤال المطروح، لا توجد حلقة ذاتية، لذلك من الواضح أن الإدخالات القطرية للمصفوفة المجاورة للرسم البياني أعلاه ستكون 0. الرسم البياني أعلاه هو رسم بياني مرجح غير موجه. سيتم تمثيل الأوزان الموجودة على حواف الرسم البياني كمدخلات لمصفوفة الجوار.
مصفوفة الجوار للرسم البياني أعلاه ستكون -
السؤال 2 - ماذا ستكون مصفوفة الجوار للرسم البياني المرجح الموجه أدناه؟
حل - في السؤال المطروح، لا توجد حلقة ذاتية، لذلك من الواضح أن الإدخالات القطرية للمصفوفة المجاورة للرسم البياني أعلاه ستكون 0. الرسم البياني أعلاه هو رسم بياني موجه مرجح. سيتم تمثيل الأوزان الموجودة على حواف الرسم البياني كمدخلات لمصفوفة الجوار.
مصفوفة الجوار للرسم البياني أعلاه ستكون -
نأمل أن تكون هذه المقالة مفيدة لك لفهم مصفوفة الجوار. لقد ناقشنا هنا مصفوفة الجوار بالإضافة إلى إنشائها وخصائصها. لقد ناقشنا أيضًا تكوين مصفوفة المجاورة على الرسوم البيانية الموجهة أو غير الموجهة، سواء كانت مرجحة أم لا.