الدرس 7 من 7
تلخيص درس المخططات الجزئية
الدرس باختصار
المخطط الجزئي مخطط نبنيه من بعض رؤوس مخطط آخر وبعض حافاته. نتعلّم هنا تعريفه بدقّة، وكيف نرسم مخططين جزئيين من أي مخطط معطى، وكيف نتحقّق أن مخططًا ما جزئي أو لا، وأن المخطط الجزئي لا يشترط أن يكون متصلًا.
مصطلحات الدرس
- المخطط الجزئي
- مخطط تنتمي جميع رؤوسه وحافاته إلى مخطط آخر.
- المخطط البسيط
- مخطط لا يحوي حلقات (حافة تبدأ وتنتهي عند الرأس نفسه) ولا حافات متعددة بين الرأسين نفسيهما.
- المخطط المتصل
- مخطط يوجد فيه طريق يصل بين كل رأسين من رؤوسه.
أهم الأفكار
تعريف المخطط الجزئي
المخطط الجزئي من المخطط هو مخطط كل رؤوسه من رؤوس وكل حافاته من حافات . لا نضيف رأسًا جديدًا ولا حافة غير موجودة في ، ولا نغيّر الرأسين اللذين تصل بينهما الحافة.
طريقة رسم مخطط جزئي
نختار أولًا مجموعة من الرؤوس (كلها أو بعضها)، ثم نختار حافات من بين الحافات الموجودة فعلًا في المخطط الأصلي بين هذه الرؤوس، ويجوز أن نحذف بعض الحافات حتى بين الرؤوس المختارة. يوجد عادةً كثير من المخططات الجزئية لمخطط واحد، فنأخذ أي اثنين منها.
لا يشترط الاتصال
قد يكون المخطط الجزئي غير متصل، مثل أن نأخذ رأسًا لا نصله بحافة أو نأخذ حافتين متباعدتين. وإذا كان المخطط الأصلي بسيطًا فكل مخطط جزئي منه بسيط.
اختبار المخطط الجزئي
نمرّ على كل رأس في المخطط المقترَح فنتأكد أنه في الأصل، ثم على كل حافة فنتأكد أنها حافة بين الرأسين نفسيهما في الأصل. إذا وُجد رأس جديد، أو عدد رؤوس أكبر من الأصل، أو حافة غير موجودة، فهو ليس مخططًا جزئيًا.
أمثلة محلولة
مثال 1: رسم مخططين جزئيين
المخطط رؤوسه وحافاته . أرسم مخططين جزئيين منه.
اعرض الحل
- المخطط الأول: نأخذ الرؤوس والحافات فيتكوّن مثلث، وكلها من .
- المخطط الثاني: نأخذ الرؤوس والحافتين فيتكوّن مسار (متصل).
- كل رأس وكل حافة في المخططين موجودة في فهما جزئيان.
الجواب: مثلث ومسار
مثال 2: اختبار مخطط مقترَح
المخطط رؤوسه وحافتاه و. هل هو مخطط جزئي من في المثال السابق؟
اعرض الحل
- الرؤوس كلها في .
- الحافة موجودة في .
- الحافة غير موجودة في (لا حافة بين و)، فالمخطط ليس جزئيًا.
الجواب: لا
مثال 3: أكبر عدد حافات في مخطط جزئي على رؤوس معيّنة
في المخطط نفسه، ما أكبر عدد حافات يمكن أن تكون في مخطط جزئي رؤوسه ؟
اعرض الحل
- نجمع الحافات الموجودة في بين هذه الرؤوس الأربعة فقط: .
- الحافة ليست بينها لأن خارج الرؤوس المختارة.
- عددها ، وأخذها كلها يعطي أكبر مخطط جزئي على هذه الرؤوس.
الجواب:
مثال 4: مخطط جزئي غير متصل
أرسم مخططًا جزئيًا غير متصل من .
اعرض الحل
- نأخذ الرؤوس .
- نأخذ الحافتين و فقط (ولا نأخذ ).
- لا طريق من إلى في هذا المخطط، فهو غير متصل، لكنه جزئي لأن كل رأس وحافة فيه من .
الجواب: رؤوس وحافتان و
أخطاء شائعة
إضافة حافة غير موجودة في المخطط الأصلي.
ليش غلط: كل حافة في المخطط الجزئي يجب أن تكون من الأصل.
الصح: نراجع قائمة حافات الأصل قبل الرسم.
الاعتقاد أن المخطط الجزئي يجب أن يكون متصلًا.
ليش غلط: التعريف يشترط انتماء الرؤوس والحافات فقط.
الصح: نقبل رأسًا منفردًا أو مكوّنات منفصلة.
أخذ رؤوس أكثر من رؤوس المخطط الأصلي.
ليش غلط: لا يمكن أن يحوي الجزئي رأسًا غير موجود في الأصل.
الصح: نقارن عدد الرؤوس وأسماءها بالأصل.
اختبر حالك
1. هل يمكن أن يحوي مخطط جزئي رأسًا إذا كانت رؤوس المخطط الأصلي ؟
اعرض الجواب
الجواب: لا
لا يجوز استعمال رأس غير موجود في الأصل.
2. هل يجب أن يكون المخطط الجزئي متصلًا؟
اعرض الجواب
الجواب: لا
التعريف لا يشترط الاتصال.
3. في المخطط السابق، كم حافة في أكبر مخطط جزئي رؤوسه ؟
اعرض الجواب
الجواب:
الحافات .
جاهز تتدرّب؟
6 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.
تدرّب على 6 سؤال من هالدرس مجانًا