الدرس 5 من 7
تلخيص درس المخططات
الدرس باختصار
المُخطَّط (graph) طريقة بصرية لتمثيل الروابط بين أشياء مختلفة: مدن تصل بينها طرق، أو محطات باص، أو أجهزة حاسوب متصلة بشبكة. نتعلّم هنا مكوّنات المُخطَّط وكيف نحسب درجات رؤوسه ونصنّف المسارات داخله.
مصطلحات الدرس
- الرأس (vertex)
- نقطة في المُخطَّط تمثّل شيئًا مثل مدينة أو محطة، ولا يُعدّ تقاطع حافتين رأسًا.
- الحافة (edge)
- خط أو منحنى يصل بين رأسين ويمثّل الرابط بينهما.
- درجة الرأس (degree)
- عدد الحافات التي تلتقي عند هذا الرأس، والحلقة تُحسب مرّتين.
- المُخطَّط الموزون (weighted graph)
- مُخطَّط تحمل كل حافة فيه عددًا يسمّى وزنها، مثل المسافة أو الزمن أو التكلفة.
- الممشى (walk)
- سلسلة حافات متتالية تبدأ كل واحدة منها حيث تنتهي سابقتها، ويجوز تكرار الحافات والرؤوس.
- الممر (trail) والطريق (path)
- الممر ممشى لا تتكرّر فيه أي حافة، والطريق ممر لا يتكرّر فيه أي رأس.
- الدارة (circuit)
- ممر مغلق، أي أنّ رأس بدايته هو نفسه رأس نهايته.
- دارة هاملتون ودارة أويلر
- دارة هاملتون دارة تمرّ بجميع الرؤوس، ودارة أويلر ممر مغلق يشمل جميع الحافات من دون تكرار.
أهم الأفكار
مجموعة الرؤوس والحافات والدرجات
نكتب رؤوس المُخطَّط في مجموعة وحافاته في مجموعة أخرى (الحافة بين A وB نكتبها AB أو BA). درجات الرؤوس تُجمع في مجموعة الدرجات ، والدرجة زوجية أو فردية بحسب عددها.
مجموع الدرجات
كل حافة تمسّ رأسين، فمجموع درجات الرؤوس يساوي ضعف عدد الحافات: . ومنه يكون عدد الرؤوس ذات الدرجة الفردية زوجيًّا أو صفرًا.
طول المسار في المُخطَّط الموزون
طول المسار هو مجموع أوزان حافاته. لإيجاد أقصر مسار نعدّد المسارات الممكنة بلا حافات مكرّرة ونحسب طول كل منها ثم نختار الأصغر.
شرط وجود دارة أويلر
إذا كانت درجة كل رأس زوجية ويوجد ممر بين أي رأسين فإنّ المُخطَّط يحتوي على دارة أويلر.
أمثلة محلولة
مثال 1: الرؤوس والحافات والدرجات
مُخطَّط له الرؤوس والحافات . أوجد مجموعة الدرجات مرتّبةً تصاعديًّا، ثم تحقّق من علاقة مجموع الدرجات بعدد الحافات.
اعرض الحل
- الرأس P تلتقي عنده الحافتان PQ وPR، فدرجته 2.
- الرأس Q تلتقي عنده PQ وQR، فدرجته 2.
- الرأس R تلتقي عنده PR وQR وRS، فدرجته 3.
- الرأس S تلتقي عنده RS وST، فدرجته 2.
- الرأس T تلتقي عنده ST فقط، فدرجته 1.
- مجموعة الدرجات مرتّبةً هي (1, 2, 2, 2, 3) ومجموعها .
- عدد الحافات 5، و، فالعلاقة صحيحة.
الجواب: ومجموعها
مثال 2: أقصر مسار في مُخطَّط موزون
في مُخطَّط طرق بين أربع مناطق، الحافات وأوزانها بالكيلومترات هي: ، ، ، ، . أوجد أقصر مسار من A إلى D وطوله.
اعرض الحل
- نعدّد المسارات من A إلى D التي لا تكرّر حافة: ABD وABCD وACD وACBD.
- ABD: .
- ABCD: .
- ACD: .
- ACBD: .
- أصغر الأطوال هو 9، وهو للمسار ABCD.
الجواب: أقصر مسار هو ABCD وطوله km
مثال 3: إيجاد مجهول من مجموع الدرجات
مُخطَّط له 4 رؤوس و5 حافات، ودرجات رؤوسه هي . أوجد قيمة ثم اكتب الدرجات.
اعرض الحل
- مجموع الدرجات يساوي .
- نجمع الدرجات: .
- نكوّن المعادلة فنجد أي .
- نعوّض: الدرجات هي ، ومجموعها 10 كما هو مطلوب.
الجواب: والدرجات
مثال 4: الممشى والممر والطريق والدارة
في مُخطَّط حافاته (رؤوسه A وB وC وD وE)، صنّف كلًّا من: ABCDECA، وABCA، وABCDEC من حيث كونه ممشى أو ممرًّا أو طريقًا أو دارة. ثم احسب درجة الرأس C.
اعرض الحل
- ABCDECA: الحافات AB وBC وCD وDE وEC وCA لا تتكرّر، فهو ممر. الرأس C تكرّر فيه، فليس طريقًا. وبدايته A ونهايته A، فهو ممر مغلق، أي دارة. وهو يشمل جميع الحافات الست مرّة واحدة، فهو دارة أويلر.
- ABCA: الحافات AB وBC وCA لا تتكرّر ولا الرؤوس، وبدايته ونهايته A، فهو دارة.
- ABCDEC: الحافات لا تتكرّر لكنّ الرأس C تكرّر، فهو ممر وليس طريقًا ولا دارة.
- درجة C: تلتقي عنده الحافات BC وCA وCD وEC، فدرجته 4.
الجواب: ABCDECA دارة أويلر، وABCA دارة، وABCDEC ممر وليس طريقًا؛ ودرجة C تساوي
أخطاء شائعة
اعتبار نقطة تقاطع حافتين رأسًا.
ليش غلط: الرأس يمثّل شيئًا في المسألة، أمّا تقاطع حافتين في الرسم فلا يمثّل شيئًا.
الصح: عدّ رأسًا فقط النقاط المرسومة أو المسمّاة على أنّها رؤوس.
عدّ الحلقة حافة واحدة عند حساب درجة الرأس.
ليش غلط: الحلقة تبدأ من الرأس وتنتهي عنده فتُحسب في الاتجاهين.
الصح: أضف 2 إلى درجة الرأس لكل حلقة عنده.
الخلط بين الممر والطريق.
ليش غلط: الممر يمنع تكرار الحافات فقط، أمّا الطريق فيمنع تكرار الرؤوس أيضًا.
الصح: افحص أولًا الحافات ثم الرؤوس: حافة مكرّرة تعني ممشى، ورأس مكرّر مع حافات غير مكرّرة يعني ممرًّا.
الخلط بين دارة هاملتون ودارة أويلر.
ليش غلط: هاملتون يمرّ بجميع الرؤوس، وأويلر يشمل جميع الحافات من دون تكرار.
الصح: اسأل: هل أغطّي كل الرؤوس أم كل الحافات؟
اختبر حالك
1. مُخطَّط له 7 حافات. ما مجموع درجات رؤوسه؟
اعرض الجواب
الجواب:
مجموع الدرجات يساوي ضعف عدد الحافات: .
2. مُخطَّط له 5 رؤوس ودرجاتها وعدد حافاته 8. ما قيمة ؟
اعرض الجواب
الجواب:
مجموع الدرجات ، وبما أنّ فإنّ .
3. في مُخطَّط موزون، مسار يمرّ بحافات أوزانها . ما طوله؟
اعرض الجواب
الجواب:
طول المسار هو مجموع أوزان حافاته: .
جاهز تتدرّب؟
70 سؤال على هالدرس، بتتصحّح خطوة خطوة، ومعها تلميحات لما تعلق. أول أسئلة مجانية.
تدرّب على 70 سؤال من هالدرس مجانًا