المخططات

• تعرُّف المُخطط، ومُكوّناته، وبعض التعريفات الأساسية المُتعلّقة به.
• إيجاد درجة كل رأس من رؤوس مُخطط مُعطى، وتعرُّف العلاقة بين درجات الرؤوس وعدد الحافات، واستعمالها لحلّ المسائل.

المُخطط: رؤوس تربطها حافات

• تنطوي العديد من المواقف الحياتية على روابط بين أشخاص أو أماكن أو أشياء مختلفة.
• فمثلاً، ترتبط المدن بعضها ببعض عبر الطرق، وتتصل أجهزة الحاسوب بعضها ببعض عبر شبكات الإنترنت

• يُعبَّر عن هذه الأشياء بعُقَد تُسمّى الرؤوس ⁨(vertices)⁩

فكيف نقرأ مُخططًا من الحياة اليومية؟

هل يُعدّ الشكل المجاور مُخطّطًا؟

أصف ما تُمثّله كلّ من الرؤوس والحافات في المُخطّط.

أُحدّد المحطّات التي ستمرّ بها إحدى الطائرات التابعة للشركة في رحلة من الرأس $M_1$ إلى الرأس $M_6$ (أذكر حلّين مختلفين).

حين تحمل الحافة وزنًا: المُخطط الموزون

• وتُمثل هذه القِيَم مقاييس عديدة، مثل: المسافة، والتكلفة، والزمن.

• يُمكن استعمال المُخطّطات الموزونة لحلّ العديد من المسائل الحياتية والعلمية
• مثل تحديد المسار الذي يُمكن به الوصول من موقع إلى آخر في إحدى المدن عبر أقصر مسار مُمكن، أو بأقل تكلفة مُمكنة.

• المسار المباشر بين رأسين في مُخطَّط هو الحافة بين هذين الرأسين (إن وُجدت).
• طول المسار هو مجموع أوزان حافاته.

فكيف نجد أقصر مسار بين منطقتين؟

طرق: يُبيِّن الشكل المجاور مُخطَّطًا للطرق الرئيسة بين مجموعة من المدن، ويُمثِّل العدد على كل حافةٍ الزمن (بالساعات) الذي تستغرقه سيارة في قطع المسافة بين كل مدينتين:

أُحدِّد الزمن الذي تستغرقه السيارة في قطع المسار المباشر بين المدينة ⁦B⁩ والمدينة ⁦E⁩.

أُحدِّد أقل زمن تستغرقه السيارة في الوصول من المدينة ⁦A⁩ إلى المدينة ⁦F⁩، والمسار الذي تتبعه في هذه الرحلة.

مجموعة الرؤوس والحافات ودرجة الرأس

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

• فمثلاً، مجموعة رؤوس المُخطَّط ⁦R⁩ المجاور هي: {⁦A, B, C, E⁩}.

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

• فمثلاً، درجة الرأس ⁦A⁩ في المُخطَّط ⁦R⁩ أعلاه هي 2، ودرجة الرأس ⁦B⁩ في المُخطَّط نفسه هي 3

• إذا كانت درجة الرأس عددًا زوجيًا، فإنَّها تُسمَّى درجة زوجية
• أمَّا إذا كانت عددًا فرديًا، فإنَّها تُسمَّى درجة فردية.
• فمثلاً، للرأس ⁦B⁩ في المُخطَّط ⁦R⁩ المجاور درجة فردية، وللرأس ⁦C⁩ فيه درجة زوجية.

• فمثلاً، مجموعة الدرجات للمُخطَّط ⁦R⁩ أعلاه هي:

هل تُعدُّ نقطة تقاطع الحافة ⁦FH⁩ مع الحافة ⁦EG⁩ رأسًا؟ أُبرِّر إجابتي.

أَتأمَّل المُخطَّط ⁦G⁩ المجاور، ثمَّ أُجيب عن كلّ ممَّا يأتي:

أُحدِّد مجموعة الرؤوس ومجموعة الحافات.

أُحدِّد درجة كل رأس، ونوعها.

أُحدِّد مجموعة الدرجات للمُخطَّط.

مجموع الدرجات يساوي ضعف عدد الحافات

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

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

• حيث $\text{deg } V_k$ درجة الرأس $V_k$.

فكيف نستعمل العلاقة على مُخطط مرسوم؟

نتيجة للمفهوم الأساسي المجاور؛ فإنَّ عدد الرؤوس ذات الدرجة الفردية يجب أن يكون زوجيًا أو 0، لماذا؟

أجد مجموع درجات رؤوس المُخطط المجاور.

مُخطط له 5 رؤوس و6 حافات، ودرجات رؤوسه هي: $x, x^2+2, 3x-1, 3x, 2x+1$.

أجد قيمة المُتغيّر $x$.

وماذا لو كانت بعض الدرجات مجهولة؟

ممشى، ممر، طريق، دارة: من الأعم إلى الأخص

• فمثلاً، ⁦ABCEBA⁩ ممشى في المُخطط المجاور.

• فمثلاً، ⁦EABEC⁩ ممر في المُخطط المجاور.

• فمثلاً، ⁦EABC⁩ طريق في المُخطط المجاور.

• فمثلاً، ⁦ABEA⁩ دارة في المُخطط المجاور.

• فمثلاً، ⁦ABCEA⁩ دارة هاملتون في المُخطط المجاور.

• فمثلاً، ⁦ABCDECA⁩ دارة أويلر في المُخطط المجاور.

• فمثلاً، ⁦EE⁩ حلقة في المُخطط المجاور.

• فمثلاً، الحافات المُتعدّدة في المُخطط المجاور تربط بين الرأس ⁦E⁩ والرأس ⁦C⁩.

ولنطبّق هذه التعريفات معًا على مُخطط واحد.

أُحَدِّدُ فيهِ مَمْشى لا يُمَثِّلُ مَمَرًّا، ومَمَرًّا لا يُمَثِّلُ طَريقًا، ودارَةً، ودارَةَ هامِلتونَ (إِنْ وُجِدَت)، ودارَةَ أويلَرَ (إِنْ وُجِدَت).

ثبّت ما تعلّمته على مُخططات جديدة

أَتَأَمَّلُ الشَّكلَ المُجاوِرَ الَّذي يُبَيِّنُ عَلاقاتِ الصَّداقَةِ الَّتي تَربِطُ بَينَ مَجموعَةٍ مِنَ الفَتياتِ في أَحَدِ مَواقِعِ التَّواصُلِ الاجتِماعيِّ، ثُمَّ أُجيبُ عَن كُلٍّ مِمَّا يَأتي:

هَل يُعَدُّ الشَّكلُ المُجاوِرُ مُخَطَّطًا؟

أَصِفُ ما تُمَثِّلُهُ كُلٌّ مِنَ الرُّؤوسِ والحافاتِ في المُخَطَّطِ.

كَم صَديقَةً لِلانا في هذا المَوقِعِ؟

مَنِ الصَّديقاتُ المُشتَرَكاتُ بَينَ عَبير ودانية؟

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

أَجِدُ تَكلِفَةَ ذَهابِ مَندوبِ المَبيعاتِ في مَسارٍ مُباشِرٍ مِنَ المُحافَظَةِ ⁦A⁩ إِلى المُحافَظَةِ ⁦B⁩، ثُمَّ إِلى المُحافَظَةِ ⁦C⁩.

أُحَدِّدُ أَقَلَّ تَكلِفَةٍ لِلذَّهابِ مِنَ المُحافَظَةِ ⁦B⁩ إِلى المُحافَظَةِ ⁦D⁩، ثُمَّ أُحَدِّدُ المَسارَ الَّذي اتَّخَذتُهُ لِذَلِكَ.

أَتَأَمَّلُ المُخَطَّطَ المُجاوِرَ، ثُمَّ أُجيبُ عَن كُلٍّ مِمَّا يَأتي:

أُحَدِّدُ مَجموعَةَ الرُّؤوسِ ومَجموعَةَ الحافاتِ.

أُحَدِّدُ دَرَجَةَ كُلِّ رَأْسٍ، ونَوعَها.

أُحَدِّدُ مَجموعَةَ الدَّرَجاتِ لِلمُخَطَّطِ.

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

مُخَطَّطٌ لَهُ 5 رُؤوسٍ و9 حافاتٍ، ودَرَجاتُ رُؤوسِهِ هي: $x, 2x, x^2+1, x+2, x+1$. أَجِدُ قيمَةَ المُتَغَيِّرِ $x$.

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

إرشاد: عِندَ استِعمالِ صِيغَةِ مَجموعِ دَرَجاتِ الرُّؤوسِ، تُعَدُّ الحَلَقَةُ حافَةً واحِدَةً.

أُحَدِّدُ في المُخَطَّطِ مَمْشى لا يُمَثِّلُ مَمَرًّا، ومَمَرًّا لا يُمَثِّلُ طَريقًا، وطَريقًا، ودارَةً، ودارَةَ هامِلتونَ (إِنْ وُجِدَت)، ودارَةَ أويلَرَ (إِنْ وُجِدَت).

أَتَأَمَّلُ المُخَطَّطَ المُجاوِرَ، ثُمَّ أُحَدِّدُ فيهِ:

مَمْشى لا يُمَثِّلُ مَمَرًّا.

مَمَرًّا لا يُمَثِّلُ طَريقًا.

خَمسَةَ طُرُقٍ مِن ⁦B⁩ إِلى ⁦D⁩.

دارَةً.

طرق: يُبَيِّنُ الشَّكلُ المُجاوِرُ مُخَطَّطًا لِلطُّرُقِ الرَّئيسَةِ الَّتي تَصِلُ بَينَ مَجموعَةٍ مِنَ المَناطِقِ في إِحدى المُدُنِ، ويُمَثِّلُ العَدَدُ عَلى كُلِّ حافَةٍ المَسافَةَ (بالكيلومتر) بَينَ مَنطِقَتَينِ:

أُحَدِّدُ طولَ أَقْصَرِ مَسارٍ بَينَ المَنطِقَةِ ⁦A⁩ والمَنطِقَةِ ⁦Z⁩، ثُمَّ أُحَدِّدُ المَسارَ الَّذي اتَّخَذتُهُ لِذَلِكَ.

أَجِدُ دارَةً تَبدأُ بالرَّأسِ ⁦B⁩، وتَنتَهي بِهِ، ثُمَّ أَجِدُ طولَها بالكيلومتر.

أَجِدُ دارَةَ هامِلتونَ، ثُمَّ أَجِدُ طولَها بالكيلومتر.

جُسور: يُبَيِّنُ الشَّكلُ المُجاوِرُ مُخَطَّطًا لِلمَسأَلَةِ الوارِدَةِ في بَند (مَسأَلَةِ اليَومِ).

أَستَعينُ بالمُخَطَّطِ وما تَعَلَّمتُهُ في هذا الدَّرسِ عَن دارَةِ أويلَرَ لِلإِجابَةِ عَنِ المَسأَلَةِ، ثُمَّ أُبَرِّرُ إِجابَتي.

مهارات التفكير العليا مَسأَلَةٌ مَفتوحَةٌ: أَرسُمُ مُخَطَّطًا يُحَقِّقُ الوَصفَ المُعطى في كُلٍّ مِمَّا يَأتي:

يَتَضَمَّنُ المُخَطَّطُ 4 رُؤوسٍ، و6 حافاتٍ.

يَتَضَمَّنُ المُخَطَّطُ 5 رُؤوسٍ، و8 حافاتٍ تُمَثِّلُ إِحداها حَلَقَةً.

يَتَضَمَّنُ المُخَطَّطُ 4 رُؤوسٍ دَرَجاتُها فَردِيَّةٌ، ورَأْسًا دَرَجَتُهُ زَوجِيَّةٌ.

يَتَضَمَّنُ المُخَطَّطُ 3 رُؤوسٍ دَرَجَةُ كُلٍّ مِنها 2، ورَأْسَينِ دَرَجَةُ كُلٍّ مِنهُما 1.

يَتَضَمَّنُ المُخَطَّطُ رَأسَينِ دَرَجَةُ كُلٍّ مِنهُما 2، ورَأْسًا دَرَجَتُهُ 3، ورَأْسًا دَرَجَتُهُ 1.

يَتَضَمَّنُ المُخَطَّطُ 4 رُؤوسٍ دَرَجَةُ كُلٍّ مِنها 5، و3 رُؤوسٍ دَرَجَةُ كُلٍّ مِنها 2.

تَحَدٍّ: أَتَأَمَّلُ المُخَطَّطَ المُجاوِرَ، ثُمَّ أُجيبُ عَنِ السُّؤالَينِ الآتِيَينِ:

أُحَدِّدُ دارَةَ هامِلتونَ في المُخَطَّطِ.

أُحَدِّدُ دارَةَ أويلَرَ في المُخَطَّطِ.