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