كيفية إنشاء رسم بياني باستخدام مصفوفة الجوار: التعليمات والأمثلة

الرسوم البيانية هي واحدة من الهياكل الأساسية في نظرية الرسم البياني وتستخدم على نطاق واسع في مختلف المجالات مثل علوم الكمبيوتر والرياضيات والفيزياء وحتى علم الاجتماع. مهمة مهمة عند العمل مع الرسوم البيانية هي إنشاء تصورهم. في هذه المقالة ، سننظر في إحدى طرق بناء الرسم البياني-باستخدام مصفوفة الجوار.

المصفوفة المجاورة هي مصفوفة ثنائية الأبعاد تمثل فيها الصفوف والأعمدة رؤوس الرسم البياني ، وتشير عناصر المصفوفة إلى وجود أو عدم وجود اتصال بين الرؤوس. وبالتالي ، سيكون كل عنصر من عناصر المصفوفة مساويا لـ 1 إذا كانت هناك حافة بين الرؤوس المقابلة ، و 0 إذا لم تكن هناك حافة.

لإنشاء رسم بياني باستخدام مصفوفة الجوار ، من الضروري تصور كل رأس من الرسم البياني وربطها بالحواف وفقا لمصفوفة الجوار. للقيام بذلك ، يمكنك استخدام أدوات مختلفة ، مثل مكتبات الرسومات أو الخدمات عبر الإنترنت.

مثال: ضع في اعتبارك مصفوفة الجوار لرسم بياني به 4 رؤوس:

[ 0 1 0 1 ]

[ 1 0 1 0 ]

[ 0 1 0 1 ]

[ 1 0 1 0 ]

1. ما هي مصفوفة الجوار وكيفية استخدامها
2. كيفية إنشاء مصفوفة مجاورة فارغة للرسم البياني
3. كيفية ملء مصفوفة المجاورة مع قائمة من الحواف
4. كيفية ملء مصفوفة الجوار من ملف نصي
5. أمثلة على بناء الرسم البياني باستخدام مصفوفة الجوار
6. سؤال وجواب
7. ما هي المصفوفة المجاورة للرسم البياني?
8. في أي الحالات تكون مصفوفة الجوار غير ملائمة لتمثيل الرسم البياني?
9. هل من الممكن إنشاء رسم بياني بناء على مصفوفة الجوار بقيم سالبة في الخلايا?

ما هي مصفوفة الجوار وكيفية استخدامها

مصفوفة الجوار هي إحدى طرق تمثيل الرسم البياني في شكل جدول. يتم استخدامه لتخزين المعلومات حول الاتصالات بين رؤوس الرسم البياني. مصفوفة الجوار هي مصفوفة ثنائية الأبعاد حيث تتوافق الصفوف والأعمدة مع رؤوس الرسم البياني. يشير عنصر المصفوفة إلى وجود أو عدم وجود حافة بين الرؤوس.

تعد مصفوفة الجوار مفيدة لحل عدد من المهام ، مثل العثور على المسارات في الرسم البياني ، والتحقق من الاتصال ، وتحديد وجود الدورات ، وغير ذلك الكثير. كما أنها مريحة لتصور وتحليل هيكل الرسم البياني.

لاستخدام مصفوفة الجوار ، اتبع الخطوات التالية:

1. تقديم قائمة من جميع القمم من الرسم البياني.
2. إنشاء مصفوفة مربعة الحجم ن س ن ، أين ن هو عدد الرؤوس.
3. املأ المصفوفة بقيم تشير إلى وجود أو عدم وجود حافة بين الرؤوس. عادة ما يتم قبول الإشارة إلى وجود حافة بقيمة 1 ، والغياب بقيمة 0.

مثال على مصفوفة الجوار:

في هذا المثال ، يتكون الرسم البياني من ثلاثة رؤوس محددة بالحروف أ ، ب و ج. توجد حافة بين الرؤوس أ و ب ، وهناك أيضا حافة بين الرؤوس أ و ج. لا توجد حافة بين الرؤوس ب و ج.

وبالتالي ، فإن مصفوفة الجوار تجعل من السهل تحديد وجود الحواف والوصلات بين رؤوس الرسم البياني. بل هو أداة مريحة لتحليل والعمل مع الرسوم البيانية.

كيفية إنشاء مصفوفة مجاورة فارغة للرسم البياني

مصفوفة الجوار هي جدول يستخدم لتمثيل الرسم البياني كمصفوفة ثنائية الأبعاد. في مصفوفة الجوار ، يتم تقديم معلومات حول الروابط بين رؤوس الرسم البياني كعناصر مصفوفة. من الضروري إنشاء مصفوفة مجاورة فارغة للرسم البياني لملئها بمعلومات حول الاتصالات.

لإنشاء مصفوفة مجاورة فارغة ، من الضروري:

1. تحديد عدد رؤوس الرسم البياني. سيحدد هذا المبلغ بعد المصفوفة.
2. إنشاء صفيف ثنائي الأبعاد مع الأبعاد المطلوبة. للقيام بذلك ، يمكنك استخدام لغة برمجة (على سبيل المثال ، بايثون ، سي)) ، أو إنشاء جدول للقيم الفارغة يدويا.

مثال على إنشاء مصفوفة مجاورة فارغة للرسم البياني:

في هذا المثال ، مصفوفة الجوار لها بعد 4 4 4 ، لأن الرسم البياني يحتوي على 4 رؤوس. تمتلئ جميع عناصر المصفوفة بالأصفار ، لأنه في الحالة الأولية لا يحتوي الرسم البياني على اتصالات بين الرؤوس.

بعد إنشاء مصفوفة مجاورة فارغة ، يمكنك ملؤها بمعلومات حول الاتصالات بين رؤوس الرسم البياني. للقيام بذلك ، يتم تعيين العناصر المقابلة للمصفوفة على قيمة أخرى غير الصفر.

كيفية ملء مصفوفة المجاورة مع قائمة من الحواف

يعد إنشاء رسم بياني باستخدام قائمة الحواف إحدى طرق تمثيل الرسوم البيانية. قائمة الحافة عبارة عن مجموعة من أزواج الرؤوس المتصلة بحافة. على سبيل المثال ، ستبدو قائمة الحواف للرسم البياني بثلاثة رؤوس أ ، ب ، ج وحافتين بين أ و ب ، و ب و ج ، كما يلي: {(أ ، ب) ، (ب ، ج)}.

لملء مصفوفة الجوار باستخدام قائمة الحافة ، اتبع الخطوات التالية:

1. قم بإنشاء مصفوفة مجاورة فارغة للحجم ن س ن ، أين ن هو عدد الرؤوس في الرسم البياني.
2. انتقل من خلال قائمة الحواف.
3. لكل زوج من الرؤوس (ش, الخامس) من قائمة الحافة ، قم بتعيين القيمة 1 في مصفوفة الجوار في الخلايا (ش, الخامس) و (الخامس, ش).
4. إذا كان الرسم البياني غير موجه ، فإنه يكفي لملء واحدة فقط من الخلايا (ش ، الخامس) أو (الخامس ، ش) مع القيمة 1.
5. إذا كان الرسم البياني مرجحا ، فبدلا من القيمة 1 ، يجب كتابة وزن الحافة في خلية مصفوفة الجوار.

مثال على إنشاء مصفوفة مجاورة بناء على قائمة الحواف:

قائمة الحواف: {(أ ، ب) ، (ب ، ج) ، (ج ، أ)}

مصفوفة الجوار الناتجة هي:

أ ب ج

0 1 1

ب 1 0 1

جيم 1 1 0

في هذا المثال ، يتكون الرسم البياني من ثلاثة رؤوس — أ ، ب ، ج. تربط الحواف الرؤوس أ و ب ، ب ، ج ، ج و أ. في فهارس الصفوف والأعمدة ، تتوافق المصفوفات مع رؤوس الرسم البياني. تشير قيمة 1 في الخلية (أ ، ب) و (ب ، أ) إلى وجود حافة بين القمم أ و ب.

وبالتالي ، باستخدام قائمة الحواف ، من الملائم ملء مصفوفة الجوار وتقديم الرسم البياني كجدول.

كيفية ملء مصفوفة الجوار من ملف نصي

مصفوفة الجوار هي جدول تتوافق فيه الصفوف والأعمدة مع رؤوس الرسم البياني. تشير الإدخالات في الجدول إلى الرؤوس التي تحتوي هذه القمة على حواف بها. لملء مصفوفة الجوار من ملف نصي ، يمكنك اتباع الخطوات التالية:

1. افتح ملف نصي للقراءة.
2. احسب عدد رؤوس الرسم البياني من السطر الأول من الملف.
3. قم بإنشاء مصفوفة ثنائية الأبعاد (مصفوفة) بالحجم المطلوب لتخزين مصفوفة الجوار.
4. اقرأ الأسطر المتبقية من الملف واملأ مصفوفة الجوار بالقيم المناسبة.

مثال على كود بايثون:

مواطنه مقروءة_جاسة_المصفوفة (اسم الملف):

ملف = فتح (اسم الملف ، "ص")

عدد الرؤوس = كثافة العمليات (ملف.قراءة الخط())

مجاور_المصفوفة = [[0] * رؤوس الأرقام لـ _ في النطاق(رؤوس الأرقام)]

لأني في النطاق (رؤوس الأرقام):

خط = ملف.قراءة الخط ().قطاع ().split()

for j in range(num_vertices):

adjacency_matrix[i][j] = int(line[j])

file.close()

return adjacency_matrix

file_name = "graph.txt"

matrix = read_adjacency_matrix(file_name)

В данном примере предполагается, что текстовый файл содержит матрицу смежности для графа. يجب أن يحتوي السطر الأول من الملف على عدد رؤوس الرسم البياني ، ويجب أن تحتوي الخطوط المتبقية على قيم عناصر مصفوفة الجوار مفصولة بمسافات.

سيتم تخزين المصفوفة المجاورة للرسم البياني.

أمثلة على بناء الرسم البياني باستخدام مصفوفة الجوار

فيما يلي بعض الأمثلة على كيفية إنشاء الرسوم البيانية باستخدام مصفوفة الجوار.

مثال 1:

لنفترض أن لدينا مصفوفة الجوار التالية:

في هذه الحالة ، تشير كل قيمة للمصفوفة إلى وجود (1) أو غياب (0) للاتصال بين الرؤوس المقابلة. وبالتالي ، يمكننا إنشاء الرسم البياني التالي:

• يتم توصيل قمة الرأس 1 إلى القمم 2 و 3
• يتم توصيل فيرتكس 2 إلى القمم 1 و 4
• يتم توصيل قمة الرأس 3 إلى القمم 1 و 4
• يتم توصيل قمة الرأس 4 إلى القمم 2 و 3

وبالتالي ، سيبدو الرسم البياني كما يلي:

1 --- 2

| |

| |

3 --- 4

المثال 2:

الآن فكر في مصفوفة مجاورة أخرى:

بناء على هذه المصفوفة ، يمكننا إنشاء الرسم البياني التالي:

• قمة الرأس أ متصل بالرؤوس ب و هـ
• قمة الرأس ب متصل بالرؤوس أ, ج و د
• قمة الرأس ج متصل بالرؤوس ب و هـ
• فيرتكس د متصل فقط فيرتكس ب
• قمة الرأس ه متصل بالرؤوس أ و ج

سيبدو الرسم البياني كما يلي:

أ - - - ب - - - ج

| |

| |

هاء (د)

وبالتالي ، يمكن للمرء أن يرى كيف يمكن استخدام مصفوفة الجوار لإنشاء رسم بياني.

سؤال وجواب

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

المصفوفة المجاورة للرسم البياني هي مصفوفة مربعة تتوافق فيها الصفوف والأعمدة مع رؤوس الرسم البياني ، وتشير قيم الخلية إلى وجود حافة بين الرؤوس المقابلة أم لا. إذا كانت الحافة موجودة ، فإن قيمة الخلية هي 1 ، وإلا فهي 0.

في أي الحالات تكون مصفوفة الجوار غير ملائمة لتمثيل الرسم البياني?

قد تكون مصفوفة الجوار غير ملائمة لتمثيل رسم بياني في الحالات التي يحتوي فيها الرسم البياني على عدد كبير من الرؤوس والحواف ، لأن المصفوفة تتطلب تخصيص الذاكرة لكل زوج محتمل من الرؤوس. أيضا ، إذا كان الرسم البياني متناثرا ، أي أنه يحتوي على حواف قليلة ، فقد تكون مصفوفة الجوار غير فعالة من حيث الذاكرة وتعقيد العمليات.

هل من الممكن إنشاء رسم بياني بناء على مصفوفة الجوار بقيم سالبة في الخلايا?

لا يمكن أن تحتوي مصفوفة الجوار للرسم البياني على قيم سالبة في الخلايا ، حيث يتم استخدام القيمتين 0 و 1 في هذا السياق للإشارة إلى وجود أو عدم وجود حافة. القيم السلبية لا معنى لعرض الاتصالات بين القمم.