تعرَّفْتُ في الدرس السابق مفهوم المُخطَّط ومُكوِّناته وبعض التعريفات الأساسية المُتعلِّقة به، وسأتعرَّف في هذا الدرس بعض الأنواع الخاصة من المُخطَّطات.
المُخطَّط البسيط، والمُخطَّط المتصل، والمُخطَّط الجزئي
يُطلَق على المُخطَّط الذي لا توجد فيه حلقة أو حافات مُتعدِّدة اسم المُخطَّط البسيط أمّا المُخطَّط المتصل فهو مُخطَّط يمتاز بوجود طريق يصل بين كل رأسين من رؤوسه.
أنظر الشكل الآتي الذي يُبيِّن مُخطَّطًا متصلًًا ومُخطَّطًا آخرَ غير متصل.
وأمّا المُخطَّط الجزئي من مُخطَّط ما فهو مُخطَّط تنتمي جميع رؤوسه وحافاته إلى هذا المُخطَّط. في ما يأتي مُخطَّطات جزئية من المُخطَّط R المُبيَّن في الشكل المجاور.
المُخطَّط الكامل، والمُخطَّط المُكمِّل
المُخطَّط الكامل هو مُخطَّط بسيط يتصل كل رأسين فيه بحافة واحدة، ويُرمَز إلى المُخطَّط الكامل الذي يحوي n من الرؤوس بالرمز Kn . أنظر الشكل الآتي الذي يُبيِّن المُخطَّط K4 والمُخطَّط K5
وأمّا المُخطَّط البسيط الذي عدد رؤوسه مساوٍ لعدد رؤوس المُخطَّط البسيط G، وليكن n والذي تكون مجموعة حافاته هي جميع الحافات الموجودة في المُخطَّط Kn وغير الموجودة في المُخطَّط G، فيُسمّى المُخطَّط المُكمِّل للمُخطَّط ،G
ويُرمَز إليه بالرمز . أنظر الشكل الآتي الذي يُبيِّن المُخطَّط G والمُخطَّط المُكمِّل له .
الشجرة، والشجرة الشاملة
يُطلَق على المُخطَّط المتصل الذي لا يحوي أيَّ دارة اسم الشجرة في ما يأتي ثلاثة مُخطَّطات يُعَدُّ كلٌّ منها شجرة:
تُسمّى الشجرة T شجرة شاملة للمُخطَّط المتصل G إذا كانت T مُخطَّطًا جزئيًّا من G، وتحوي جميع رؤوسه كما هو مُبيَّن في الشكل الآتي.
أصغر شجرة شاملة
تعلَّمْتُ في المثال السابق إيجاد أشجار شاملة لمُخطَّط متصل. ولكنْ، كيف يُمكِن إيجاد أصغر شجرة شاملة للمُخطَّط المتصل الموزون؟
يُمكِن إيجاد أصغر شجرة شاملة للمُخطَّط المتصل الموزون باستعمال خوارزمية برايم ، التي يُمكِن بها تحديد أقصر طريقة وأسرعها لربط جميع الرؤوس في المُخطَّط المتصل الموزون، بحيث يكون مجموع أوزان الحافات في هذه الشجرة الشاملة أقل ما يُمكِن.
1 اختيار أيِّ رأس في المُخطَّط لبَدْء رسم (إنشاء) الشجرة.
2 تحديد أقل حافة وزنًا تربط بين رأس موجود في الشجرة ورأس لم يُضَفْ بعدُ إلى الشجرة. وفي حال وجود حافات عديدة لها الوزن نفسه، فإنَّه يُمكِن اختيار أيٍّ منها. وإذا شكَّلت الحافة دارة، فإنَّها لا تضاف إلى الشجرة.
3 تكرار الخطوة الثانية حتّى تكتمل إضافة جميع الرؤوس، ويتمَّ ربطها بالشجرة.
4 كتابة الحافات المضافة إلى الشجرة بالترتيب.
تمثيل المُخطَّطات باستعمال المصفوفات
تعرَّفْتُ في الدرس السابق أنَّ المُخطَّط تمثيل بياني يُستعمَل للتعبير عن روابط بين أشياء باستعمال رؤوس وحافات. ولكنْ يُمكِن أيضًا التعبير عن هذه الروابط باستعمال المصفوفات. فمث اًل، يُمكِن التعبير عن المُخطَّطات غير الموزونة باستعمال مصفوفة الجوار ؛ وهي مصفوفة مُربَّعة رتبتها n × n ، ومُدخَلاتها عدد الحافات التي تربط بين كل رأسين في المُخطَّط، إضافةً إلى عدد الحافات التي تربط الرؤوس بنفسها (الحلقات).
أمّا المُخطَّطات الموزونة فيُمكِن التعبير عنها باستعمال مصفوفة الوزن؛ وهي مصفوفة مُربَّعة رتبتها n × n ، ومُدخَلاتها أوزان الحافات التي تربط بين كل رأسين في المُخطَّط، إضافةً إلى أوزان الحافات التي تربط الرؤوس بنفسها (الحلقات).
