مصطلحات درس المخططات
8 مصطلحات مع تعريفاتها، كما بتحتاجها بالامتحان.
- الرأس (vertex)
- نقطة في المُخطَّط تمثّل شيئًا مثل مدينة أو محطة، ولا يُعدّ تقاطع حافتين رأسًا.
- الحافة (edge)
- خط أو منحنى يصل بين رأسين ويمثّل الرابط بينهما.
- درجة الرأس (degree)
- عدد الحافات التي تلتقي عند هذا الرأس، والحلقة تُحسب مرّتين.
- المُخطَّط الموزون (weighted graph)
- مُخطَّط تحمل كل حافة فيه عددًا يسمّى وزنها، مثل المسافة أو الزمن أو التكلفة.
- الممشى (walk)
- سلسلة حافات متتالية تبدأ كل واحدة منها حيث تنتهي سابقتها، ويجوز تكرار الحافات والرؤوس.
- الممر (trail) والطريق (path)
- الممر ممشى لا تتكرّر فيه أي حافة، والطريق ممر لا يتكرّر فيه أي رأس.
- الدارة (circuit)
- ممر مغلق، أي أنّ رأس بدايته هو نفسه رأس نهايته.
- دارة هاملتون ودارة أويلر
- دارة هاملتون دارة تمرّ بجميع الرؤوس، ودارة أويلر ممر مغلق يشمل جميع الحافات من دون تكرار.