حل اسئلة درس أنواع خاصة من المخططات
١٧ سؤالاً من تمارين الكتاب، مع رقم الصفحة والحل
افتح الموضوع في التطبيق- سؤال من الكتاب · صفحة 94إنترنت: يبيّن الشكل المجاور مخطّطا لشبكة إنترنت تصل بين مجموعة من الحواسيب في إحدى المكتبات العامة. وفيه يمثّل العدد على كل حافة طول الكبل (بالمتر) بين كل جهازي حاسوب في المكتبة. أستعمل خوارزمية برايم لإيجاد أصغر شجرة شاملة للمخطّط، ثمّ أجد أقل تكلفة لربط جميع الحواسيب في المكتبة، علما بأنّ تكلفة تمديد المتر الواحد من الكبل 3 JD.
إظهار الحلّإخفاء الحلّ
وزن أصغر شجرة شاملة =1+1+2+2+2+2+4+6+10=30\,m، وأقل تكلفة =30\times 3=90 JD - سؤال من الكتاب · صفحة 94أتأمّل مصفوفة الجوار المجاورة، ثمّ أجيب عن كلّ ممّا يأتي: \begin{bmatrix} 0 & 1 & 1 & 2 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{bmatrix} هل يحتوي المخطّط الممثّل بمصفوفة الجوار المجاورة على حلقات؟ أبرّر إجابتي.
إظهار الحلّإخفاء الحلّ
لا، لا يحتوي على حلقات؛ لأنّ جميع مدخلات القطر الرئيس في مصفوفة الجوار أصفار. - سؤال من الكتاب · صفحة 94أتأمّل مصفوفة الجوار المجاورة، ثمّ أجيب عن كلّ ممّا يأتي: \begin{bmatrix} 0 & 1 & 1 & 2 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{bmatrix} هل المخطّط الممثّل بمصفوفة الجوار المجاورة بسيط؟ أبرّر إجابتي.
إظهار الحلّإخفاء الحلّ
لا، المخطّط ليس بسيطا؛ لأنّ فيه حافتين بين الرأس الأول والرأس الرابع (المدخلة 2)، أي حافات متعدّدة. - سؤال من الكتاب · صفحة 94أحدّد المخطّط الكامل ممّا يأتي، وأسمّيه بالرموز، ثمّ أبرّر إجابتي. (A) (B) (C) (D)
إظهار الحلّإخفاء الحلّ
المخطّط (A) كامل، ويسمّى K_4؛ لأنّه بسيط وكل رأسين من رؤوسه الأربعة متصلان بحافة واحدة (6 حافات). - سؤال من الكتاب · صفحة 107إذا كان وزن أصغر شجرة شاملة للمخطّط الآتي، تمرّ بالحافة التي وزنها k، هو 33، فإنّ قيمة الثابت k تساوي:
إظهار الحلّإخفاء الحلّ
5 - سؤال من الكتاب · صفحة 94أتأمّل المخطّط المجاور (رؤوسه A، B، C، D، E، F، G، H، R)، ثمّ أجيب: هل المخطّط بسيط؟ أبرّر إجابتي.
إظهار الحلّإخفاء الحلّ
نعم؛ لأنه لا يحوي حلقات أو حافات متعددة - سؤال من الكتاب · صفحة 94أتأمّل المخطّط المجاور (رؤوسه A، B، C، D، E، F، G، H، R)، ثمّ أجيب: هل المخطّط متصل؟ أبرّر إجابتي.
إظهار الحلّإخفاء الحلّ
نعم، المخطط متصل؛ لأنّه يوجد طريق بين كل رأسين من رؤوسه - سؤال من الكتاب · صفحة 94أتأمّل المخطّط المجاور (رؤوسه A، B، C، D، E، F، G، H، R)، ثمّ أجيب: هل المخطّط كامل؟ أبرّر إجابتي.
إظهار الحلّإخفاء الحلّ
لا، المخطّط ليس كاملا؛ لأنّه توجد رؤوس غير متصلة بحافة، مثل A و C. - سؤال من الكتاب · صفحة 94أتأمّل المخطّط المجاور (رؤوسه A، B، C، D، E، F، G)، ثمّ أجيب: هل المخطّط بسيط؟ أبرّر إجابتي.
إظهار الحلّإخفاء الحلّ
نعم، المخطّط بسيط؛ لأنّه لا يحتوي على حلقات ولا على حافات متعدّدة. - سؤال من الكتاب · صفحة 94أتأمّل المخطّط المجاور (رؤوسه A، B، C، D، E، F، G)، ثمّ أجيب: هل المخطّط متصل؟ أبرّر إجابتي.
إظهار الحلّإخفاء الحلّ
لا، المخطّط غير متصل؛ لأنّه لا يوجد طريق بين بعض الرؤوس، مثل A و D (يتكوّن من جزأين منفصلين: A,B,C و D,E,F,G). - سؤال من الكتاب · صفحة 109أتأمّل المخطّط الآتي، ثمّ أجيب عن كلّ ممّا يلي: هل المخطّط متصل؟ أبرّر إجابتي.
إظهار الحلّإخفاء الحلّ
المخطط متصل، لأنه يمكن إيجاد طريق يصل بين كل رأسين من رؤوسه. - سؤال من الكتاب · صفحة 109أتأمّل المخطّط الآتي، ثمّ أجيب عن كلّ ممّا يلي: هل المخطّط بسيط؟ أبرّر إجابتي.
إظهار الحلّإخفاء الحلّ
المخطط بسيط، لأنه لا يحتوي حافات متعددة ولا حلقات. - سؤال من الكتاب · صفحة 94أمثّل المخطّط الموزون الآتي (رؤوسه F، G، H، N، W، S، M) بمصفوفة الوزن
إظهار الحلّإخفاء الحلّ
رتبة 7\times7، ترتيب الرؤوس F,G,H,N,W,S,M: \begin{bmatrix}- & 0.5 & - & - & - & - & - \\ 0.5 & - & 0.3 & 0.3 & 0.2 & - & - \\ - & 0.3 & - & 0.4 & - & - & - \\ - & 0.3 & 0.4 & - & 0.1 & 0.6 & 0.4 \\ - & 0.2 & - & 0.1 & - & - & - \\ - & - & - & 0.6 & - & - & 0.5 \\ - & - & - & 0.4 & - & 0.5 & -\end{bmatrix} - سؤال من الكتاب · صفحة 94أمثّل المخطّط الموزون الآتي (رؤوسه من A إلى H) بمصفوفة الوزن
إظهار الحلّإخفاء الحلّ
رتبة 8\times8، ترتيب الرؤوس A,\dots,H: \begin{bmatrix}- & 4 & - & 7 & - & - & - & - \\ 4 & - & 1 & - & - & - & - & 2 \\ - & 1 & - & - & - & - & - & 1 \\ 7 & - & - & - & 6 & - & - & - \\ - & - & - & 6 & - & 5 & - & 3 \\ - & - & - & - & 5 & - & 5 & 2 \\ - & - & - & - & - & 5 & - & - \\ - & 2 & 1 & - & 3 & 2 & - & -\end{bmatrix} - سؤال من الكتاب · صفحة 94أمثّل المخطّط الآتي (رؤوسه V1، V2، V3، V4) بمصفوفة الجوار
إظهار الحلّإخفاء الحلّ
رتبة 4\times4، ترتيب الرؤوس V_1,V_2,V_3,V_4: \begin{bmatrix}0 & 1 & 2 & 1 \\ 1 & 0 & 0 & 1 \\ 2 & 0 & 0 & 2 \\ 1 & 1 & 2 & 0\end{bmatrix} - سؤال من الكتاب · صفحة 94أمثّل المخطّط الآتي (رؤوسه A، B، C، D) بمصفوفة الجوار
إظهار الحلّإخفاء الحلّ
رتبة 4\times4، ترتيب الرؤوس A,B,C,D: \begin{bmatrix}0 & 3 & 0 & 2 \\ 3 & 0 & 1 & 1 \\ 0 & 1 & 2 & 2 \\ 2 & 1 & 2 & 0\end{bmatrix} - سؤال من الكتاب · صفحة 109أمثّل المخطّط الآتي بمصفوفة الوزن.
إظهار الحلّإخفاء الحلّ
\begin{matrix} & A & B & C & D & E \\ A & - & 5 & - & - & 10 \\ B & 5 & - & 8 & - & 2 \\ C & - & 8 & - & 1 & - \\ D & - & - & 1 & - & 5 \\ E & 10 & 2 & - & 5 & - \end{matrix}