شرح الموضوع
أنواع خاصة من المخططات
- تعرّف أنواع خاصة من المخططات.
- تعرّف مصفوفة الجوار، واستعمالها للتعبير عن الروابط في المخططات.
- تعرّف مصفوفة الوزن، واستعمالها لتمثيل العلاقات بين الرؤوس في مخطط موزون.
المخطط ليس شكلًا واحدًا: له أنواع خاصة
تعرّفتُ في الدرس السابق مفهوم المخطط ومكوّناته وبعض التعريفات الأساسية المتعلقة به، وسأتعرّف في هذا الدرس بعض الأنواع الخاصة من المخططات.
المخطط البسيط، والمخطط المتصل، والمخطط الجزئي
البسيط والمتصل والجزئي: ثلاث صفات للمخطط
- في ما يأتي مخططات جزئية من المخطط R المبيّن في الشكل المجاور.
مثال 1
a) هل المخطط بسيط؟ أبرّر إجابتي.
b) هل المخطط متصل؟ أبرّر إجابتي.
c) أرسم مخططين جزئيين من المخطط.
المخطط الكامل، والمخطط المكمّل
الكامل والمكمّل: كل رأسين متصلان، أو العكس
مثال 2
a) أُحدّد المُخطّط الكامل ممّا يأتي، وأُسمّيه بالرموز، ثمّ أُبرّر إجابتي.
b) أرسم للمُخطّط المجاور.
الشجرة والشجرة الشاملة
الشجرة: مخطط متصل بلا أي دارة
مثال 3
- عدد حافات الشجرة الشاملة للمُخطّط المتصل يساوي عدد رؤوس المُخطّط () مطروحًا منه (1)، ويمكن التعبير عنه بالرموز كالآتي:
أرسم شجرتين شاملتين للمُخطّط المجاور.
أصغر شجرة شاملة
أقل كلفة لربط كل الرؤوس: خوارزمية برايم
- ولكن، كيف يُمكن إيجاد أصغر شجرة شاملة للمُخطّط المتصل الموزون؟
هل يُمكن للشجرة أن تحتوي على حافات متعدّدة أو حلقات؟ أُبرّر إجابتي.
أنابيب مياه: يُبيّن الشكل المجاور مُخطّطًا لشبكة أنابيب مياه تصل بين المحطّات الرئيسة في إحدى المدن. وفيه يُمثّل العدد على كل حافة طول الأنبوب (بالكيلومتر) بين كل محطّتين في المدينة:
a) أستعمل خوارزمية برايم لإيجاد أصغر شجرة شاملة للمُخطّط، ثمّ أكتب الحافات التي أضيفت إليها بالترتيب.
b) أستعمل إجابة السؤال السابق لإيجاد أقل طول من الأنابيب يلزم لربط جميع المحطّات في المدينة.
خوارزمية برايم
- يُمكن إيجاد أصغر شجرة شاملة لمُخطّط متصل موزون باستعمال خوارزمية برايم، وذلك باتباع الخطوات الآتية:
- اختيار أيّ رأس في المُخطّط لبدء رسم (إنشاء) الشجرة.
- تحديد أقل حافة وزنًا تربط بين رأس موجود في الشجرة ورأس لم يُضف بعدُ إلى الشجرة.
- وفي حال وجود حافات عديدة لها الوزن نفسه، فإنّه يُمكن اختيار أيّ منها.
- وإذا شكّلت الحافة دارة، فإنّها لا تُضاف إلى الشجرة.
- تكرار الخطوة الثانية حتّى تكتمل إضافة جميع الرؤوس، ويتمّ ربطها بالشجرة.
- كتابة الحافات المضافة إلى الشجرة بالترتيب.
مثال 4 : من الحياة
تمثيل المُخطّطات باستعمال المصفوفات
المصفوفة تحوّل المخطط إلى جدول أرقام
- ولكن يُمكن أيضًا التعبير عن هذه الروابط باستعمال المصفوفات.
- فمثلاً، يُمكن التعبير عن المُخطّطات غير الموزونة باستعمال مصفوفة الجوار
مثال 5
a) أمثّل المُخطّط الآتي بمصفوفة الجوار.
b) أمثّل المُخطّط الآتي بمصفوفة الوزن.
- ما دلالة مجموع مُدخلات كل صف في مصفوفة الجوار؟
- ما دلالة مجموع كل عمود في مصفوفة الجوار؟
أتدرب وأحل المسائل
تدرّب على كل نوع من المخططات
أَتأمَّل المُخطَّط المُجاور، ثمَّ أُجيب عن كلٍّ ممَّا يأتي:
- هل المُخطَّط بسيط؟ أُبرِّر إجابتي.
- هل المُخطَّط متصل؟ أُبرِّر إجابتي.
- هل المُخطَّط كامل؟ أُبرِّر إجابتي.
- أرسم مُخطَّطين جزئيين من المُخطَّط.
- أرسم شجرة شاملة للمُخطَّط.
- هل المُخطَّط بسيط؟ أُبرِّر إجابتي.
- هل المُخطَّط متصل؟ أُبرِّر إجابتي.
- أرسم مُخطَّطين جزئيين من المُخطَّط.
- أُحدِّد المُخطَّط الكامل ممَّا يأتي، وأُسمِّيه بالرموز، ثمَّ أُبرِّر إجابتي.
أرسم المُخطَّط المُكمِّل لكلٍّ من المُخطَّطات الآتية:
10.
11.
إنترنت: يُبيِّن الشكل المُجاور مُخطَّطاً لشبكة إنترنت تصل بين مجموعة من الحواسيب في إحدى المكتبات العامة. وفيه يُمثِّل العدد على كل حافة طول الكَبْل (بالمتر) بين كل جهازي حاسوب في المكتبة. أُجيب عن السؤالين الآتيين تباعاً:
- أستعمل خوارزمية برايم لإيجاد أصغر شجرة شاملة للمُخطَّط، ثمَّ أكتب الحافات التي أُضيفت إلى الشجرة بالترتيب.
- أستعمل إجابة السؤال السابق لإيجاد أقل تكلفة لربط جميع الحواسيب في المكتبة، علماً بأنَّ تكلفة تمديد المتر الواحد من الكَبْل 3 JD.
أُمثِّل كل مُخطَّط ممَّا يأتي بمصفوفة الجوار:
14.
15.
أُمثِّل كل مُخطَّط ممَّا يأتي بمصفوفة الوزن:
16.
17.
أَتأمَّل مصفوفة الجوار المُجاورة، ثمَّ أُجيب عن كلٍّ ممَّا يأتي:
- هل يحتوي المُخطَّط المُمثَّل بمصفوفة الجوار المُجاورة على حلقات؟ أُبرِّر إجابتي.
- هل المُخطَّط المُمثَّل بمصفوفة الجوار المُجاورة بسيط؟ أُبرِّر إجابتي.
- أرسم المُخطَّط المُمثَّل في مصفوفة الجوار المُجاورة.
- تُمثِّل مصفوفة الوزن المُجاورة أطوال أنابيب المياه (بالمتر) التي تصل بين المرشات في إحدى المزارع. أرسم المُخطَّط الموزون الذي تُمثِّله المصفوفة.
مهارات التفكير العليا
أرسم وأبرّر: أسئلة مفتوحة وتحدٍّ
مسألة مفتوحة: أرسم كُلّاً ممَّا يأتي:
- مُخطَّط كامل، عدد رؤوسه 7
- مُخطَّط متصل، عدد رؤوسه 6، ودرجة كلٍّ منها 3
- مُخطَّط بسيط، غير متصل، عدد رؤوسه 6، ودرجة كلٍّ منها 2
- تبرير: أرسم المُخطَّط المُكمِّل للمُخطَّط المُجاور، ثمَّ أُبرِّر إجابتي.
- تحدٍّ: أرسم جميع الأشجار الشاملة التي يُمكن أن تنتج من المُخطَّط الآتي:
