رياضيات الأعمال، الصف الثاني عشر (حقل الأعمال) · الخوارزميات ونظرية المخططات · المخططات الخاصة والأشجاربطاقات مراجعة: المخططات الخاصة والأشجار12 بطاقة: اقرأ الوجه، جاوب بعقلك، واقلب البطاقة.اقلب كل البطاقات1المُخطَّط البسيطمُخطَّط لا توجد فيه حلقة ولا حافات مُتعدِّدة بين رأسين.2المُخطَّط المتصلمُخطَّط يوجد فيه طريق يصل بين كل رأسين من رؤوسه.3المُخطَّط الكامل KnK_nKnمُخطَّط بسيط فيه nnn رأسًا، ويتصل كل رأسين فيه بحافة واحدة.4المُخطَّط المُكمِّلمُخطَّط له رؤوس G نفسها، وحافاته هي الحافات الموجودة في KnK_nKn وغير الموجودة في G.5الشجرةمُخطَّط متصل لا يحوي أيَّ دارة.6الشجرة الشاملةشجرة هي مُخطَّط جزئي من مُخطَّط متصل G وتحوي جميع رؤوس G.7مصفوفة الجوارمصفوفة مُربَّعة مُدخَلاتها عدد الحافات بين كل رأسين، وتُحسب الحلقة فيها مرتين.8مصفوفة الوزنمصفوفة مُربَّعة مُدخَلاتها أوزان الحافات بين الرؤوس، ويدل الرمز – على عدم وجود اتصال.9الشجرة الشاملةالشجرة متصلة وبلا دارات. وتحوي الشجرة الشاملة لمُخطَّط من nnn رأسًا كل رؤوسه، ويمكن أن يكون للمُخطَّط الواحد عدة أشجار شاملة.10خوارزمية برايملإيجاد أصغر شجرة شاملة لمُخطَّط موزون متصل: ابدأ من أي رأس، ثم أضف دائمًا أقل حافة وزنًا تصل رأسًا داخل الشجرة برأس خارجها، ولا تُضِف حافة تكوّن دارة. كرّر حتى تدخل كل الرؤوس. الوزن الكلي هو مجموع أوزان الحافات المضافة.11المُكمِّللرسم G‾\overline{G}G ارسم KnK_nKn ثم احذف منه حافات G. وإذا جمعنا حافات G وحافات G‾\overline{G}G نحصل على KnK_nKn.12المصفوفاترتبة المصفوفة n×nn \times nn×n حيث nnn عدد الرؤوس، ولكل رأس صف وعمود. في مصفوفة الجوار يدل 0 على عدم وجود حافة. في مصفوفة الوزن يُكتب الوزن، ويُكتب – عند عدم الاتصال.بدّك تحفظها للامتحان؟سجّل مجاناً، وفهيم برجّعلك البطاقات اللي بتنساها بالوقت المناسب، وبتبلّش بالأفكار اللي غلطت فيها.سجّل مجاناً وراجع مع فهيم اقرأ تلخيص الدرس · كل مصطلحات الدرس بصفحة وحدة · ورقة مراجعة للطباعة