رياضيات الأعمال، الصف الثاني عشر (حقل الأعمال) · الخوارزميات ونظرية المخططات

ورقة مراجعة: المخططات الخاصة والأشجار

أهم أفكار الدرس ومصطلحاته وقوانين الوحدة بمكان واحد. اطبعها وراجع منها قبل الامتحان.

أهم الأفكار

  1. الشجرة الشاملة الشجرة متصلة وبلا دارات. وتحوي الشجرة الشاملة لمُخطَّط من nn رأسًا كل رؤوسه، ويمكن أن يكون للمُخطَّط الواحد عدة أشجار شاملة.
  2. خوارزمية برايم لإيجاد أصغر شجرة شاملة لمُخطَّط موزون متصل: ابدأ من أي رأس، ثم أضف دائمًا أقل حافة وزنًا تصل رأسًا داخل الشجرة برأس خارجها، ولا تُضِف حافة تكوّن دارة. كرّر حتى تدخل كل الرؤوس. الوزن الكلي هو مجموع أوزان الحافات المضافة.
  3. المُكمِّل لرسم G‾\overline{G} ارسم KnK_n ثم احذف منه حافات G. وإذا جمعنا حافات G وحافات G‾\overline{G} نحصل على KnK_n.
  4. المصفوفات رتبة المصفوفة n×nn \times n حيث nn عدد الرؤوس، ولكل رأس صف وعمود. في مصفوفة الجوار يدل 0 على عدم وجود حافة. في مصفوفة الوزن يُكتب الوزن، ويُكتب – عند عدم الاتصال.

مصطلحات الدرس

المُخطَّط البسيط
مُخطَّط لا توجد فيه حلقة ولا حافات مُتعدِّدة بين رأسين.
المُخطَّط المتصل
مُخطَّط يوجد فيه طريق يصل بين كل رأسين من رؤوسه.
المُخطَّط الكامل KnK_n
مُخطَّط بسيط فيه nn رأسًا، ويتصل كل رأسين فيه بحافة واحدة.
المُخطَّط المُكمِّل
مُخطَّط له رؤوس G نفسها، وحافاته هي الحافات الموجودة في KnK_n وغير الموجودة في G.
الشجرة
مُخطَّط متصل لا يحوي أيَّ دارة.
الشجرة الشاملة
شجرة هي مُخطَّط جزئي من مُخطَّط متصل G وتحوي جميع رؤوس G.
مصفوفة الجوار
مصفوفة مُربَّعة مُدخَلاتها عدد الحافات بين كل رأسين، وتُحسب الحلقة فيها مرتين.
مصفوفة الوزن
مصفوفة مُربَّعة مُدخَلاتها أوزان الحافات بين الرؤوس، ويدل الرمز – على عدم وجود اتصال.

قوانين الخوارزميات ونظرية المخططات

جدول التتبع
نضع عمودًا لرقم الخطوة وعمودًا لكل متغير وعمودًا للمطبوع؛ والتعليمة x=2x+1x=2x+1 تعني استبدال قيمة xx بالقيمة الجديدة وليست معادلة.
أشكال مخطط سير العمليات
المستطيل للتعليمات، والمعيّن للقرار (نعم أو لا)، والمستطيل بزوايا مستديرة للبداية والنهاية، ومتوازي الأضلاع للإدخال والإخراج.
خوارزمية حل المعادلة التربيعية
d=b2−4ac,x=−b±d2ad=b^2-4ac,\quad x=\frac{-b\pm\sqrt{d}}{2a}
إذا كان d<0d<0 فلا حلول حقيقية، وإذا كان d=0d=0 فالحل x=−b2ax=\frac{-b}{2a}، وإذا كان d>0d>0 فللمعادلة حلان.
الحد الأدنى لعدد الصناديق
⌈مجموع المقاساتسعة الصندوق⌉\left\lceil\frac{\text{مجموع المقاسات}}{\text{سعة الصندوق}}\right\rceil
نقرّب الناتج إلى الأعلى دائمًا، فإن ساوى عدد صناديق حلّنا هذا العدد فالحل أمثل.
خوارزمية الملاءمة الأولى
نلتزم ترتيب العناصر المعطى، ونضع كل عنصر في أول صندوق يتسع له، ونفتح صندوقًا جديدًا إذا لم يتسع أي صندوق.
خوارزمية الملاءمة المتناقصة
نرتّب العناصر تنازليًّا أولًا ثم نطبّق الملاءمة الأولى؛ وهي أفضل عادة لكنها لا تضمن الحل الأمثل.
خوارزمية الصندوق الكامل
نملأ أولًا صناديق من عناصر مجموعها يساوي السعة تمامًا، ثم نعبّئ الباقي بالملاءمة الأولى.
حساب المهدور
المهدور=(عدد الصناديق×السعة)−مجموع المقاسات\text{المهدور}=(\text{عدد الصناديق}\times\text{السعة})-\text{مجموع المقاسات}
المهدور هو المساحة الفارغة الكلية في الصناديق المستعملة.
تصنيف المخطط بدرجات الرؤوس
المخطط المتصل الذي درجات رؤوسه كلها زوجية أويلري، وإن كان فيه رأسان فرديان فقط فهو شبه أويلري، وغير ذلك لا يكون أيًّا منهما.
أقصر مسار أويلري في مخطط أويلري
L=مجموع أوزان الحافاتL=\text{مجموع أوزان الحافات}
نمرّ على كل حافة مرة واحدة فقط فلا نكرر شيئًا.
أقصر مسار أويلري في مخطط شبه أويلري
L=الوزن الكلي+أقصر طريق بين الرأسين الفرديينL=\text{الوزن الكلي}+\text{أقصر طريق بين الرأسين الفرديين}
نكرّر حافات أقصر طريق بين الرأسين الفرديين.
مخطط فيه أكثر من رأسين فرديين
نجرّب كل طرائق ازدواج الرؤوس الفردية ونختار الطريقة التي مجموع أوزان طرقها أقل، ثم نضيفه إلى الوزن الكلي.
مجموع درجات الرؤوس
∑deg⁡Vk=2E\sum\deg V_k=2E
كل حافة تمس رأسين فمجموع الدرجات ضعف عدد الحافات.
عدد الرؤوس الفردية
عدد الرؤوس ذات الدرجة الفردية في أي مخطط زوجي أو صفر.
طول المسار في مخطط موزون
طول المسار هو مجموع أوزان حافاته.
شرط وجود دارة أويلر
إذا كانت درجة كل رأس زوجية ويوجد ممر بين أي رأسين فللمخطط دارة أويلر.
الشجرة الشاملة
E=n−1E=n-1
الشجرة متصلة وبلا دارات، والشجرة الشاملة لمخطط من nn رأسًا تحوي كل رؤوسه وn−1n-1 حافة.
خوارزمية برايم لأصغر شجرة شاملة
نبدأ من رأس، ونضيف دائمًا أقل حافة وزنًا تصل رأسًا داخل الشجرة برأس خارجها دون تكوين دارة.
مكمل المخطط
E(G)+E(G‾)=n(n−1)2E(G)+E(\overline{G})=\frac{n(n-1)}{2}
المخطط التام KnK_n فيه n(n−1)2\frac{n(n-1)}{2} حافة، وحافات GG مع حافات مكمله G‾\overline{G} تعطي KnK_n.
مصفوفة الجوار
رتبتها n×nn\times n حيث nn عدد الرؤوس، والعنصر 11 إذا وُجدت حافة بين الرأسين و00 إذا لم توجد.
مصفوفة الوزن
نكتب وزن الحافة في الموضع المناظر ونكتب −- حيث لا يوجد اتصال.

من اُدرُس: odrosai.com/ar/subjects/JO-MATH-BUS/units/2/bus-special_graphs_trees

بدك تتأكد إنك فاهم؟

سجّل مجاناً وحلّ أسئلة على هالدرس، بتتصحّح خطوة خطوة ومعها تلميحات لما تعلق.