الرسوم البيانية والشبكات
مُقدَّم| English | العربية |
|---|---|
| graph/ɡræf/ | الرسم البياني |
| vertices/ˈvɜːtɪsiːz/ | الرؤوس |
| edges/ˈedʒɪz/ | الحواف |
| degree/dɪˈɡriː/ | الدرجة |
| path/pæθ/ | المسار |
| cycle/ˈsaɪkl/ | الحلقة |
| connected/kəˈnektɪd/ | متصل |
| tree/triː/ | الشجرة |
| weighted graph/ˈweɪtɪd ɡræf/ | الرسم البياني الموزون |
| shortest path/ˈʃɔːtɪst pæθ/ | أقصر مسار |
نموذج الاتصال يحتاج افتراضاته
- الرسم البياني (Graph) له رؤوس وحواف. قرر ماذا تمثل وما إذا كانت الاتصالات موجهة، أو مرجحة، أو غير موجهة.
- ورقة العمل تستخدم رسوم بيانية بسيطة غير موجهة ومنتهية بدون حلقات أو حواف مكررة. لا يغير موقع الرسم اتصالاتها، لكن السهم أو وزن الحافة يمكن أن يغير النموذج الرياضي.
عد الاتصالات بشكل متسق
- الدرجة تعد الحواف المتصلة برأس في رسم بياني بسيط غير موجه. المجموع الكلي للدرجتين يساوي ضعف عدد الحواف، لذا يجب أن يكون زوجياً.
- المسار يتبع الاتصالات؛ الحلقة تعود لنقطة البداية دون تكرار الرؤوس الأخرى. يكون الرسم البياني متصلاً عندما يمكن الوصول إلى كل رأس من كل رأس آخر.
في رسم بياني بسيط غير موجه بدون حلقات، أربعة حواف يلتقي برأس. ما درجته؟
درجته هي 4، عدد الحواف الملتقطة تحت اتفاقية الرسم البياني المنصوص عليها.
الشجرة تحتاج خاصيتين
- الشجرة متصلة ولا تحتوي على حلقات. الشجرة المنتهية ذات n رأساً لها n ناقص 1 حافة.
- امتلاك n ناقص 1 حافة وحده لا يثبت أنها شجرة: مثلث بالإضافة إلى مكون منفصل من رأسين يحتوي على خمسة رؤوس وأربع حواف لكنه غير متصل ويحتوي على حلقات.
شجرة تحتوي على 4 رؤوس. كم عدد الحواف لديها؟
شجرةfinite بأربعة رؤوس لها n − 1 = 3 حواف. يعتمد هذا العد على أن الرسم البياني متصل فعلاً وخالي من الحلقات.
في شبكة غير موجهة متصلة ذات تكاليف حواف موجبة تمامًا، لماذا لا يحتوي الرتق المتصل الأقل تكلفة الذي يغطي جميع الرؤوس على أي دورة؟
إزالة أي حرف من الدورة يحافظ على الاتصال ويخفض التكلفة الإجمالية لأن وزنها موجب تمامًا. وبالتالي، لا يمكن أن يكون الرتق الدوري هو الأقل تكلفة تحت هذه الافتراضات.
طرق ربط ذات تكلفة موجبة. للشبكة المتصلة ذات تكاليف الطرق الموجبة تماماً، إزالة حافة حلقة تترك الاتصال وتخفض التكلفة. إذن، الرابطة الأدنى تكلفة هي شجرة. لإيجاد شجرة التغطية الدنيا، اختر حوافاً تربط جميع الرؤوس بدون حلقة؛ اختيار أقل n ناقص 1 حافة تكلفة بشكل أعمى قد يترك مكونات منفصلة.
أقصر طريق ليس شجرة تغطية
- الرسم البياني المرجح يرتبط قيمة محددة بكل حافة. أقصر مسار يُقلل وزن الطريق بين النقطتين المعطيتين.
- شجرة التغطية الدنيا بدورها تربط كل رأس بأقل إجمالي وزن مشمول. قد يكون أقصر طريق أكثر حوافاً من طريق مباشر باهظ الثمن؛ اجمع الأوزان بدلاً من عد الحواف.
طابق كل موقف بما يجب أن تكون عليه الرؤوس والحواف الخاصة به.
تحديد تمثيل الرؤوس هو خطوة النمذجة، وهي حيث تُحسب الدرجات.
تغيير الحافة المغلقة يغير الجدوى. تكتشف الصفحة 4.5 مساراً وزنه 7، ثم تغلق حافة وتتحقق من بديل وزنه 9. لا تعيد استخدام المجموع القديم لمسار لم يعد موجوداً.
رسمان يبدو مختلفان يجب أن يكونا رسمين بيانيين مختلفين.
يمكن أن تحتوي التخطيطات المختلفة على نفس الجوار المُسمّى. قارن الاتجاهات والأوزان أيضًا عندما تكون جزءًا من الرسم البياني المحدد.
قارن جميع الهياكل ذات الصلة بالسؤال: تطابق الرؤوس، الجوار، الاتجاهات والأوزان عند التحديد. قد لا تمثل الصور المتشابهة نفس الرسم البياني؛ يمكن أن تمثل التخطيطات المختلفة نفس الاتصالات المسمّاة.