ملخص
مراجعة النقاط الرئيسية
- تتكوّن الرسوم البيانية من رؤوس وأضلاع، ويمكن تمثيلها بمجموعة رؤوس ومجموعة أضلاع.
- بالمقارنة بالعلاقات الخطية التي تجسّدها القوائم المترابطة والعلاقات التقسيمية التي تجسّدها الأشجار، تمتاز العلاقات الشبكية التي تجسّدها الرسوم البيانية بمرونة أكبر بكثير، ومن ثم فهي أكثر تعقيداً.
- في الرسوم البيانية الموجّهة تكون للأضلاع اتجاهات؛ وفي الرسوم البيانية المتصلة يمكن الوصول إلى أي رأس انطلاقاً من أي رأس آخر؛ وفي الرسوم البيانية الموزونة يحمل كل ضلع وزناً.
- تستخدم مصفوفات التجاور مصفوفات لتمثيل الرسوم البيانية، حيث يمثّل كل صف (عمود) رأساً، وتمثّل عناصر المصفوفة الأضلاع، باستخدام أو للإشارة إلى وجود ضلع بين رأسين أو عدمه. وتتمتع مصفوفات التجاور بكفاءة عالية في عمليات الإضافة والحذف والبحث والتعديل، لكنها تستهلك مساحة كبيرة.
- تستخدم قوائم التجاور عدة قوائم مترابطة لتمثيل رسم بياني: القائمة المترابطة رقم تقابل الرأس وتخزّن جميع الرؤوس المجاورة له. وبالمقارنة بمصفوفات التجاور، تستهلك قوائم التجاور مساحة أقل، لكن البحث عن الأضلاع أقل كفاءة لأن القائمة المترابطة يجب اجتيازها.
- عندما تصبح القوائم المترابطة في قوائم التجاور طويلة جداً، يمكن تحويلها إلى أشجار حمراء سوداء أو جداول تجزئة، مما يحسّن كفاءة البحث.
- من منظور خوارزمي، تجسّد مصفوفات التجاور «المقايضة بين المساحة والزمن»، بينما تجسّد قوائم التجاور «المقايضة بين الزمن والمساحة».
- يمكن استخدام الرسوم البيانية لنمذجة أنظمة واقعية متنوعة، مثل الشبكات الاجتماعية وخطوط مترو الأنفاق.
- الأشجار حالة خاصة من الرسوم البيانية، واجتياز الأشجار حالة خاصة من اجتياز الرسوم البيانية.
- يفيد البحث بالعرض في الرسوم البيانية من القريب إلى البعيد، ويتوسّع طبقةً طبقة، ويُنفَّذ عادةً باستخدام طابور.
- يسلك البحث بالعمق في الرسوم البيانية مساراً إلى أقصى عمق ممكن ويعود عند تعذّر المضي أبعد، ويُنفَّذ عادةً بالتعاود.
أسئلة وأجوبة
س: هل يُعرَّف المسار على أنه متتالية رؤوس أم متتالية أضلاع؟
تختلف التعريفات في النسخ اللغوية المختلفة من ويكيبيديا: تنص النسخة الإنجليزية على أن «المسار متتالية أضلاع»، بينما تنص النسخة الصينية على أن «المسار متتالية رؤوس». وهذا هو النص الإنجليزي الأصلي: In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices.
ويُنظر في هذا النص إلى المسار على أنه متتالية أضلاع لا متتالية رؤوس. والسبب أنه قد توجد عدة أضلاع تربط بين رأسين، وفي هذه الحالة يقابل كل ضلع مساراً.
س: في رسم بياني غير متصل، هل توجد رؤوس يتعذّر الوصول إليها؟
في رسم بياني غير متصل، إذا انطلقت من رأس واحد فسيتعذّر الوصول إلى رأس آخر على الأقل. ولاجتياز رسم بياني غير متصل تحتاج إلى عدة نقاط انطلاق بحيث تُغطّى جميع المكوّنات المتصلة.
س: في قائمة التجاور، هل يلزم ترتيب معيّن للرؤوس المجاورة لرأس ما؟
يمكن أن تظهر بأي ترتيب. غير أنها قد تحتاج عملياً إلى الترتيب وفق قواعد محددة، مثل ترتيب إضافة الرؤوس أو ترتيب قيم الرؤوس، مما يساعد على العثور سريعاً على رأس ذي قيمة متطرفة ما.