الرسم البياني الموجه مقابل الرسم غير المباشر
الرسم البياني هو هيكل رياضي يتكون من مجموعة من الرؤوس والحواف. يمثل الرسم البياني مجموعة من الكائنات (ممثلة بالرؤوس) المتصلة ببعض الروابط (ممثلة بالحواف). باستخدام الرموز الرياضية ، يمكن تمثيل الرسم البياني بواسطة G ، حيث G=(V ، E) و V هي مجموعة الرؤوس و E هي مجموعة الحواف. في الرسم البياني غير المباشر ، لا يوجد اتجاه مرتبط بالحواف التي تربط الرؤوس. في الرسم البياني الموجه يوجد اتجاه مرتبط بالحواف التي تربط الرؤوس.
رسم بياني غير موجه
كما ذكرنا سابقًا ، الرسم البياني غير الموجه هو رسم بياني لا يوجد فيه اتجاه في الحواف التي تربط الرؤوس في الرسم البياني.يصور الشكل 1 رسمًا بيانيًا غير موجه مع مجموعة من الرؤوس V={V1، V2، V3}. يمكن كتابة مجموعة من الحواف في الرسم البياني أعلاه كـ V={(V1، V2)، (V2، V3)، (V1، V3)}. يمكن ملاحظة أنه لا يوجد ما يمنع كتابة مجموعة الحواف مثل V={(V2، V1)، (V3، V2)، (V3، V1)} لأن الحواف ليس لها اتجاه. لذلك فإن الحواف في الرسم البياني غير المباشر ليست أزواجًا مرتبة. هذه هي السمة الرئيسية للرسم البياني غير المباشر. يمكن استخدام الرسوم البيانية غير الموجهة لتمثيل العلاقات المتماثلة بين الكائنات التي يتم تمثيلها بالرؤوس. على سبيل المثال ، يمكن تمثيل شبكة طريق ثنائية الاتجاه تربط مجموعة من المدن باستخدام رسم بياني غير موجه. يمكن تمثيل المدن بالرؤوس في الرسم البياني وتمثل الحواف الطرق ذات الاتجاهين التي تربط المدن.
الرسم البياني الموجه
الرسم البياني الموجه هو رسم بياني يكون فيه اتجاه الحواف في الرسم البياني الذي يربط الرؤوس. يصور الشكل 2 رسمًا بيانيًا موجهًا مع مجموعة من الرؤوس V={V1، V2، V3}. يمكن كتابة مجموعة من الحواف في الرسم البياني أعلاه كـ V={(V1، V2)، (V2، V3)، (V1، V3)}. الحواف في الرسم البياني غير المباشر هي أزواج مرتبة. بشكل رسمي ، يمكن تمثيل الحافة e في الرسم البياني الموجه بالزوج المرتب e=(x، y) حيث x هو الرأس الذي يسمى الأصل أو المصدر أو النقطة الأولية للحافة e ، والرأس y يسمى النهاية ، إنهاء قمة الرأس أو نقطة طرفية. على سبيل المثال ، يمكن تمثيل شبكة الطرق التي تربط مجموعة من المدن باستخدام طرق ذات اتجاه واحد باستخدام رسم بياني غير موجه. يمكن تمثيل المدن بالرؤوس في الرسم البياني وتمثل الحواف الموجهة الطرق التي تربط المدن مع الأخذ في الاعتبار الاتجاه الذي تتدفق فيه حركة المرور في الطريق.
ما الفرق بين الرسم البياني الموجه والرسم البياني غير الموجه؟
في الرسم البياني الموجه ، تكون الحافة زوجًا مرتبًا ، حيث يمثل الزوج المرتب اتجاه الحافة التي تربط الرأسين. من ناحية أخرى ، في الرسم البياني غير المباشر ، تعتبر الحافة زوجًا غير مرتب ، حيث لا يوجد اتجاه مرتبط بالحافة. يمكن استخدام الرسوم البيانية غير الموجهة لتمثيل العلاقات المتماثلة بين الكائنات. تتساوى كل عقدة في الرسم البياني غير المباشر في الدرجة وخارجها ولكن هذا ليس صحيحًا بالنسبة للرسم البياني الموجه. عند استخدام مصفوفة لتمثيل رسم بياني غير موجه ، تصبح المصفوفة دائمًا رسمًا بيانيًا متماثلًا ، لكن هذا لا ينطبق على الرسوم البيانية الموجهة. يمكن تحويل الرسم البياني غير المباشر إلى رسم بياني موجه عن طريق استبدال كل حافة بحافتين موجهتين في الاتجاه المعاكس. ومع ذلك ، لا يمكن تحويل الرسم البياني الموجه إلى رسم بياني غير موجه.
