رياضيات الأعمال، الصف الثاني عشر (حقل الأعمال) · الخوارزميات ونظرية المخططات
ورقة مراجعة: المخططات
أهم أفكار الدرس ومصطلحاته وقوانين الوحدة بمكان واحد. اطبعها وراجع منها قبل الامتحان.
أهم الأفكار
- مجموعة الرؤوس والحافات والدرجات نكتب رؤوس المُخطَّط في مجموعة وحافاته في مجموعة أخرى (الحافة بين A وB نكتبها AB أو BA). درجات الرؤوس تُجمع في مجموعة الدرجات ، والدرجة زوجية أو فردية بحسب عددها.
- مجموع الدرجات كل حافة تمسّ رأسين، فمجموع درجات الرؤوس يساوي ضعف عدد الحافات: . ومنه يكون عدد الرؤوس ذات الدرجة الفردية زوجيًّا أو صفرًا.
- طول المسار في المُخطَّط الموزون طول المسار هو مجموع أوزان حافاته. لإيجاد أقصر مسار نعدّد المسارات الممكنة بلا حافات مكرّرة ونحسب طول كل منها ثم نختار الأصغر.
- شرط وجود دارة أويلر إذا كانت درجة كل رأس زوجية ويوجد ممر بين أي رأسين فإنّ المُخطَّط يحتوي على دارة أويلر.
مصطلحات الدرس
- الرأس (vertex)
- نقطة في المُخطَّط تمثّل شيئًا مثل مدينة أو محطة، ولا يُعدّ تقاطع حافتين رأسًا.
- الحافة (edge)
- خط أو منحنى يصل بين رأسين ويمثّل الرابط بينهما.
- درجة الرأس (degree)
- عدد الحافات التي تلتقي عند هذا الرأس، والحلقة تُحسب مرّتين.
- المُخطَّط الموزون (weighted graph)
- مُخطَّط تحمل كل حافة فيه عددًا يسمّى وزنها، مثل المسافة أو الزمن أو التكلفة.
- الممشى (walk)
- سلسلة حافات متتالية تبدأ كل واحدة منها حيث تنتهي سابقتها، ويجوز تكرار الحافات والرؤوس.
- الممر (trail) والطريق (path)
- الممر ممشى لا تتكرّر فيه أي حافة، والطريق ممر لا يتكرّر فيه أي رأس.
- الدارة (circuit)
- ممر مغلق، أي أنّ رأس بدايته هو نفسه رأس نهايته.
- دارة هاملتون ودارة أويلر
- دارة هاملتون دارة تمرّ بجميع الرؤوس، ودارة أويلر ممر مغلق يشمل جميع الحافات من دون تكرار.
قوانين الخوارزميات ونظرية المخططات
- جدول التتبع
- نضع عمودًا لرقم الخطوة وعمودًا لكل متغير وعمودًا للمطبوع؛ والتعليمة تعني استبدال قيمة بالقيمة الجديدة وليست معادلة.
- أشكال مخطط سير العمليات
- المستطيل للتعليمات، والمعيّن للقرار (نعم أو لا)، والمستطيل بزوايا مستديرة للبداية والنهاية، ومتوازي الأضلاع للإدخال والإخراج.
- خوارزمية حل المعادلة التربيعية
- إذا كان فلا حلول حقيقية، وإذا كان فالحل ، وإذا كان فللمعادلة حلان.
- الحد الأدنى لعدد الصناديق
- نقرّب الناتج إلى الأعلى دائمًا، فإن ساوى عدد صناديق حلّنا هذا العدد فالحل أمثل.
- خوارزمية الملاءمة الأولى
- نلتزم ترتيب العناصر المعطى، ونضع كل عنصر في أول صندوق يتسع له، ونفتح صندوقًا جديدًا إذا لم يتسع أي صندوق.
- خوارزمية الملاءمة المتناقصة
- نرتّب العناصر تنازليًّا أولًا ثم نطبّق الملاءمة الأولى؛ وهي أفضل عادة لكنها لا تضمن الحل الأمثل.
- خوارزمية الصندوق الكامل
- نملأ أولًا صناديق من عناصر مجموعها يساوي السعة تمامًا، ثم نعبّئ الباقي بالملاءمة الأولى.
- حساب المهدور
- المهدور هو المساحة الفارغة الكلية في الصناديق المستعملة.
- تصنيف المخطط بدرجات الرؤوس
- المخطط المتصل الذي درجات رؤوسه كلها زوجية أويلري، وإن كان فيه رأسان فرديان فقط فهو شبه أويلري، وغير ذلك لا يكون أيًّا منهما.
- أقصر مسار أويلري في مخطط أويلري
- نمرّ على كل حافة مرة واحدة فقط فلا نكرر شيئًا.
- أقصر مسار أويلري في مخطط شبه أويلري
- نكرّر حافات أقصر طريق بين الرأسين الفرديين.
- مخطط فيه أكثر من رأسين فرديين
- نجرّب كل طرائق ازدواج الرؤوس الفردية ونختار الطريقة التي مجموع أوزان طرقها أقل، ثم نضيفه إلى الوزن الكلي.
- مجموع درجات الرؤوس
- كل حافة تمس رأسين فمجموع الدرجات ضعف عدد الحافات.
- عدد الرؤوس الفردية
- عدد الرؤوس ذات الدرجة الفردية في أي مخطط زوجي أو صفر.
- طول المسار في مخطط موزون
- طول المسار هو مجموع أوزان حافاته.
- شرط وجود دارة أويلر
- إذا كانت درجة كل رأس زوجية ويوجد ممر بين أي رأسين فللمخطط دارة أويلر.
- الشجرة الشاملة
- الشجرة متصلة وبلا دارات، والشجرة الشاملة لمخطط من رأسًا تحوي كل رؤوسه و حافة.
- خوارزمية برايم لأصغر شجرة شاملة
- نبدأ من رأس، ونضيف دائمًا أقل حافة وزنًا تصل رأسًا داخل الشجرة برأس خارجها دون تكوين دارة.
- مكمل المخطط
- المخطط التام فيه حافة، وحافات مع حافات مكمله تعطي .
- مصفوفة الجوار
- رتبتها حيث عدد الرؤوس، والعنصر إذا وُجدت حافة بين الرأسين و إذا لم توجد.
- مصفوفة الوزن
- نكتب وزن الحافة في الموضع المناظر ونكتب حيث لا يوجد اتصال.
من اُدرُس: odrosai.com/ar/subjects/JO-MATH-BUS/units/2/bus-graphs_basics
بدك تتأكد إنك فاهم؟
سجّل مجاناً وحلّ أسئلة على هالدرس، بتتصحّح خطوة خطوة ومعها تلميحات لما تعلق.
سجّل مجاناً وراجع مع فهيم اقرأ تلخيص الدرس · راجعها ببطاقات · كل مصطلحات الدرس بصفحة وحدة