الدرس 6 من 7
تلخيص درس المخططات الخاصة والأشجار
الدرس باختصار
المُخطَّط مجموعة رؤوس تصل بينها حافات، ويُستعمل لتمثيل شبكات مثل الطرق وأسلاك الكهرباء وأنابيب المياه. في هذا الدرس نتعرّف أنواعًا خاصة منه (البسيط، والمتصل، والكامل، والشجرة)، ثم نبحث عن أقل كلفة لربط كل الرؤوس، ونمثّل المُخطَّط بمصفوفة.
مصطلحات الدرس
- المُخطَّط البسيط
- مُخطَّط لا توجد فيه حلقة ولا حافات مُتعدِّدة بين رأسين.
- المُخطَّط المتصل
- مُخطَّط يوجد فيه طريق يصل بين كل رأسين من رؤوسه.
- المُخطَّط الكامل
- مُخطَّط بسيط فيه رأسًا، ويتصل كل رأسين فيه بحافة واحدة.
- المُخطَّط المُكمِّل
- مُخطَّط له رؤوس G نفسها، وحافاته هي الحافات الموجودة في وغير الموجودة في G.
- الشجرة
- مُخطَّط متصل لا يحوي أيَّ دارة.
- الشجرة الشاملة
- شجرة هي مُخطَّط جزئي من مُخطَّط متصل G وتحوي جميع رؤوس G.
- مصفوفة الجوار
- مصفوفة مُربَّعة مُدخَلاتها عدد الحافات بين كل رأسين، وتُحسب الحلقة فيها مرتين.
- مصفوفة الوزن
- مصفوفة مُربَّعة مُدخَلاتها أوزان الحافات بين الرؤوس، ويدل الرمز – على عدم وجود اتصال.
أهم الأفكار
الشجرة الشاملة
الشجرة متصلة وبلا دارات. وتحوي الشجرة الشاملة لمُخطَّط من رأسًا كل رؤوسه، ويمكن أن يكون للمُخطَّط الواحد عدة أشجار شاملة.
خوارزمية برايم
لإيجاد أصغر شجرة شاملة لمُخطَّط موزون متصل: ابدأ من أي رأس، ثم أضف دائمًا أقل حافة وزنًا تصل رأسًا داخل الشجرة برأس خارجها، ولا تُضِف حافة تكوّن دارة. كرّر حتى تدخل كل الرؤوس. الوزن الكلي هو مجموع أوزان الحافات المضافة.
المُكمِّل
لرسم ارسم ثم احذف منه حافات G. وإذا جمعنا حافات G وحافات نحصل على .
المصفوفات
رتبة المصفوفة حيث عدد الرؤوس، ولكل رأس صف وعمود. في مصفوفة الجوار يدل 0 على عدم وجود حافة. في مصفوفة الوزن يُكتب الوزن، ويُكتب – عند عدم الاتصال.
أمثلة محلولة
مثال 1: تصنيف مُخطَّط
مُخطَّط رؤوسه P, Q, R, S وحافاته PQ, QR, RS, SP, PR. هل هو بسيط؟ هل هو متصل؟ هل هو ؟ وما عدد حافات ؟
اعرض الحل
- لا توجد حلقة ولا حافتان بين الرأسين نفسيهما، فالمُخطَّط بسيط.
- يمكن الوصول من أي رأس إلى أي رأس، مثل P إلى Q إلى R إلى S، فالمُخطَّط متصل.
- في يتصل كل رأسين بحافة، وعدد الأزواج .
- المُخطَّط فيه 5 حافات فقط والحافة QS غير موجودة، فهو ليس .
الجواب: المُخطَّط بسيط ومتصل وليس كاملًا، و فيه حافات.
مثال 2: المُكمِّل
مُخطَّط بسيط G على 5 رؤوس فيه 7 حافات. كم حافة في ؟
اعرض الحل
- فيه حافات.
- حافات G وحافات معًا تكوّن حافات .
- عدد حافات يساوي .
الجواب:
مثال 3: أقل طول ربط بخوارزمية برايم
شبكة طرق تربط قرى A, B, C, D, E، وأطوال الطرق بالكيلومتر: AB = 4، AC = 2، BC = 1، BD = 5، CD = 8، CE = 10، DE = 3. جد الحافات المضافة بترتيبها بدءًا من A، ثم أقل طول طرق يربط القرى كلها.
اعرض الحل
- نبدأ من A. أقل حافة منه هي AC بوزن 2، فنضيفها.
- الحافات الواصلة من {A, C} إلى الخارج: AB = 4 وBC = 1 وCD = 8 وCE = 10. أقلها BC = 1، فنضيفها.
- الحافات من {A, B, C} إلى الخارج: BD = 5 وCD = 8 وCE = 10. أقلها BD = 5، فنضيفها.
- الحافات من {A, B, C, D} إلى E: CE = 10 وDE = 3. نضيف DE = 3.
- صارت كل الرؤوس في الشجرة، والحافات بالترتيب: AC, CB, BD, DE.
- الطول الكلي .
الجواب: الحافات: AC, CB, BD, DE، وأقل طول km
مثال 4: تمثيل مُخطَّط بمصفوفة
مُخطَّط رؤوسه A, B, C: حافة واحدة بين A وB، وحافتان بين B وC، وحلقة عند A. اكتب مصفوفة الجوار وفق الترتيب A, B, C، ثم جد مجموع مُدخَلات الصف الأول.
اعرض الحل
- الرتبة لأن عدد الرؤوس 3.
- الحلقة عند A تُحسب مرتين، فمُدخَلة (A, A) هي 2.
- مُدخَلة (A, B) هي 1 ومُدخَلة (A, C) هي 0.
- الصف الأول: ، والصف الثاني: ، والصف الثالث: .
- المصفوفة ومجموع الصف الأول .
الجواب: (وهو درجة الرأس A: حافة واحدة وحلقة تُحسب مرتين)
أخطاء شائعة
عدّ الحلقة مرة واحدة في مصفوفة الجوار.
ليش غلط: الحلقة تُحسب في الاتجاهين فتُعدّ مرتين.
الصح: اكتب 2 في مُدخَلة الرأس مع نفسه لكل حلقة.
إضافة حافة إلى الشجرة تكوّن دارة لأن وزنها هو الأقل.
ليش غلط: الشجرة لا تحوي دارات، والحافة بين رأسين موجودين أصلًا في الشجرة تكوّن دارة.
الصح: اختر أقل حافة تصل رأسًا في الشجرة برأس جديد خارجها.
ظن أن المُخطَّط الجزئي يجب أن يكون متصلًا.
ليش غلط: التعريف يشترط فقط أن تنتمي رؤوسه وحافاته إلى المُخطَّط الأصلي.
الصح: تأكد فقط أن كل رأس وكل حافة موجودة في المُخطَّط الأصلي.
اختبر حالك
1. كم حافة في المُخطَّط الكامل ؟
اعرض الجواب
الجواب:
عدد الأزواج .
2. شجرة شاملة لمُخطَّط متصل فيه 9 رؤوس، أوزان حافاتها 3, 1, 4, 2, 2, 5, 1, 3. ما وزنها الكلي؟
اعرض الجواب
الجواب:
نجمع الأوزان: .
3. في مصفوفة جوار مُخطَّط فيه 7 رؤوس، كم مُدخَلة في المصفوفة كلها؟
اعرض الجواب
الجواب:
الرتبة ، فعدد المُدخَلات .
جاهز تتدرّب؟
66 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.
تدرّب على 66 سؤال من هالدرس مجانًا