رياضيات أعمال فصل أول

المُخطَّطات

تنطوي العديد من المواقف الحياتية على روابط بين أشخاص أو أماكن أو أشياء مختلفة.

فمثاً، ترتبط المدن بعضها ببعض عبر الطرق، وتتصل أجهزة الحاسوب بعضها ببعض عبر شبكات الإنترنت، ويُمكِن التعبير عن كلٍّ من هذه الروابط بتمثيل بياني يُسمّى المُخطَّط ؛ وهو وسيلة تُظهِر كيف ترتبط الأشياء المختلفة بصريًّا، بحيث يُعبَّر عن هذه الأشياء بعُقَد تُسمّى الرؤوس ويُعبَّر عن الروابط بين الرؤوس (إنْ وُجِدت) بخطوط (أو منحنيات) متصلة تُسمّى الحافات كما يظهر في الشكل المجاور.

نظرية المُخطَّطات هي تسمية لفرع من فروع الرياضيات يُعْنى بدراسة المُخطَّطات

 

المُخطَّطات الموزونة

يُطلَق على المُخطَّط الذي يحوي قيمة مُقترِنة بكل حافة من حافاته اسم المُخطَّط الموزون، وتُمثِّل هذه القِيَم مقاييس عديدة، مثل: المسافة، والتكلفة، والزمن.

يُمكِن استعمال المُخطَّطات الموزونة لحلِّ العديد من المسائل الحياتية والعلمية، مثل تحديد المسار الذي يُمكِن به الوصول من موقع إلى آخر في إحدى المدن عبر أقصر مسار مُمكِن، أو بأقل تكلفة مُمكِنة. وبلغة المُخطَّطات، فإنَّ المسار من الرأس A إلى الرأس B هو مجموعة من الحافات، تبدأ بالرأس A، وتنتهي بالرأس B، وقد يتكرَّر في المسار أيٌّ من الرؤوس والحافات.

---

رؤوس المُخطَّط وحافاته

في ما يأتي بعض التعريفات الأساسية الخاصة بنظرية المُخطَّطات:

· مجموعة الرؤوس: مجموعة تحوي جميع رؤوس المُخطَّط. فمثاً، مجموعة رؤوس المُخطَّط R المجاور هي: .(A, B, C, E)

· مجموعة الحافات: مجموعة تحوي جميع حافات المُخطَّط. فمثاً، مجموعة حافات المُخطَّط R المجاور هي: ( AB, AE, BC, BE, CE )، حيث يُعبِّر الرمز AB مثلًًا عن الحافة بين الرأس A والرأس B.

· درجة الرأس: عدد يُعبِّر عن عدد الحافات التي تلتقي عند الرأس. فمثلًًا، درجة الرأس A في المُخطَّط R أعلاه هي 2، ودرجة الرأس B في المُخطَّط نفسه هي 3

· مجموعة الدرجات: مجموعة تحوي جميع درجات رؤوس المُخطَّط. فمث اًل، مجموعة الدرجات للمُخطَّط R أعلاه هي: deg R = (2, 2, 3, 3)

---

مجموع درجات رؤوس المُخطَّط

يُمكِن أيضًا إيجاد مجموع درجات رؤوس أيِّ مُخطَّط إذا عُلِم عدد حافاته، وذلك بضرب عدد حافاته في 2؛ لأنَّ كل حافة ترتبط برأسين.

إذا كان لمُخطَّطٍ n من الرؤوس، و E من الحافات، فإنَّه يُمكِن إيجاد مجموع درجات رؤوس هذا المُخطَّط باستعمال العلاقة الآتية:

$\sum _{k=1}^n (deg V_k )=2E$

حيث $deg V_k$ درجة الرأس $V_k$

---

الممشى والممر والطريق والدارة والحلقة في المُخطَّط

· الممشى: سلسلة من الحافات في المُخطَّط، تُمثِّل فيها نهاية كل حافةٍ بداية حافة أُخرى، ما عدا الحافة الأخيرة. فمثلًًا، ABCEBA ممشى في المُخطَّط المجاور.

· الممر : ممشى لا تتكرَّر فيه أيُّ حافة، ويُمكِن أنْ تتكرَّر فيه الرؤوس. فمثلًًا، EABEC ممر في المُخطَّط المجاور.

· الطريق: ممر لا يتكرَّر فيه أيُّ رأس. فمثلًًا، EABC طريق في المُخطَّط المجاور.

· الدارة: ممر رأس بدايته هو نفسه رأس نهايته، ولا يتكرَّر فيه أيُّ رأس، ما عدا رأس البداية ورأس النهاية. فمثلًًا، ABEA دارة في المُخطَّط المجاور.

· دارة هاملتون: دارة تحوي جميع رؤوس المُخطَّط. فمثاً، ABCEA دارة هاملتون في المُخطَّط المجاور.

· دارة أويلر : ممر رأس بدايته هو نفسه رأس نهايته، وهو يشمل جميع حافات المُخطَّط من دون تكرار. فمثلًًا، ABCDECA دارة أويلر في المُخطَّط المجاور.

· الحلقة: حافة تبدأ بالرأس نفسه، وتنتهي به. فمثاً، EE حلقة في المُخطَّط المجاور.

· الحافات المُتعدِّدة: حافتان أو مجموعة من الحافات التي تربط زوجًا من الرؤوس. فمثلًًا، الحافات المُتعدِّدة في المُخطَّط المجاور تربط بين الرأس E والرأس