نظرية البيان والشبكات

تصنيف الأوراق هنا غير رسمي وأعددناه بأنفسنا، ونطبّقه فقط حيث يطابق شكل السؤال فعلاً اتفاقية ورقة حقيقية (مثل تقسيم رياضيات IB AA بين بدون آلة حاسبة وبآلة حاسبة). لا يمثل توزيع الأوراق أو ترقيمها الرسمي في الامتحان الفعلي، والأسئلة غير المؤكدة تُصنَّف كـ«تدريب عام».

• 1لبيان بسيط رؤوس درجاتها 3، 2، 2، 3، 2. استخدم مصافحة اليد لإيجاد عدد أضلاع البيان.نمط الورقة 1سهل2 درجاتآلة حاسبة+
• 2تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لبيان بسيط رؤوس درجاتها 3، 2، 2، 3، 2. استخدم مصافحة اليد لإيجاد عدد أضلاع البيان.» وتعالج إجابته هذه النقطة فقط: «تحديد مصافحة اليد: مجموع درجات جميع الرؤوس يساوي ضعف عدد الأضلاع.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 2 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحسهل2 درجاتآلة حاسبة+
• 3اشرح لماذا لا يمكن لأي بيان بسيط أن يمتلك تسلسل الدرجات 3، 2، 2، 2.نمط الورقة 1سهل2 درجاتبدون آلة+
• 4تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «اشرح لماذا لا يمكن لأي بيان بسيط أن يمتلك تسلسل الدرجات 3، 2، 2، 2.» وتعالج إجابته هذه النقطة فقط: «حساب مجموع الدرجات المقترحة: 3 + 2 + 2 + 2 = 9.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 2 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحسهل2 درجاتبدون آلة+
• 5لبيان رؤوسه A، وB، وC، وD وأضلاعه AB، وAC، وBC، وBD. أنشئ مصفوفة التجاور لهذا البيان، وتحقق من أن مجموع كل صف يساوي درجة الرأس المقابل.نمط الورقة 1متوسط4 درجاتآلة حاسبة+
• 6تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لبيان رؤوسه A، وB، وC، وD وأضلاعه AB، وAC، وBC، وBD. أنشئ مصفوفة التجاور لهذا البيان، وتحقق من أن مجموع كل صف يساوي درجة الرأس المقابل.» وتعالج إجابته هذه النقطة فقط: «إنشاء مصفوفة التجاور 4×4 بترتيب الصفوف/الأعمدة A، وB، وC، وD: [[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]].» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 4 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحمتوسط4 درجاتآلة حاسبة+
• 7تربط شبكة ست بلدات A، وB، وC، وD، وE، وF بالطرق والمسافات التالية (كم): AB=4، AC=2، BC=1، BD=5، CD=8، CE=10، DE=2، DF=6، EF=3. استخدم خوارزمية كروسكال لإيجاد شجرة ممتدة صغرى لهذه الشبكة، مع إظهار ترتيب إضافة الأضلاع، وحدد وزنها الكلي.نمط الورقة 2صعب6 درجاتآلة حاسبة+
• 8تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «تربط شبكة ست بلدات A، وB، وC، وD، وE، وF بالطرق والمسافات التالية (كم): AB=4، AC=2، BC=1، BD=5، CD=8، CE=10، DE=2، DF=6، EF=3. استخدم خوارزمية كروسكال لإيجاد شجرة ممتدة صغرى لهذه الشبكة، مع إظهار ترتيب إضافة الأضلاع، وحدد وزنها الكلي.» وتعالج إجابته هذه النقطة فقط: «ترتيب الأضلاع تصاعدياً حسب الوزن: BC(1)، AC(2)، DE(2)، EF(3)، AB(4)، BD(5)، DF(6)، CD(8)، CE(10).» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 6 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحصعب6 درجاتآلة حاسبة+
• 9باستخدام الشبكة نفسها من السؤال السابق، طبّق خوارزمية بريم بدءاً من الرأس A لإيجاد شجرة ممتدة صغرى، مع إظهار ترتيب إضافة الرؤوس. تحقق من أن الوزن الكلي يطابق نتيجة خوارزمية كروسكال.نمط الورقة 2صعب6 درجاتآلة حاسبة+
• 10تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «باستخدام الشبكة نفسها من السؤال السابق، طبّق خوارزمية بريم بدءاً من الرأس A لإيجاد شجرة ممتدة صغرى، مع إظهار ترتيب إضافة الرؤوس. تحقق من أن الوزن الكلي يطابق نتيجة خوارزمية كروسكال.» وتعالج إجابته هذه النقطة فقط: «البدء بـA؛ أرخص ضلع من الشجرة {A} هو AC(2)، فتُضاف C.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 6 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحصعب6 درجاتآلة حاسبة+
• 11لشبكة رؤوسها P، وQ، وR، وS، وT، وU وأضلاع موزونة: PQ=7، PR=9، PU=14، QR=10، QS=15، RS=11، RU=2، ST=6، UT=9. استخدم خوارزمية ديكسترا لإيجاد أقصر مسار من P إلى T، مع تحديد المسار وطوله الكلي.نمط الورقة 3 (موسّعة)صعب7 درجاتآلة حاسبة+
• 12تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لشبكة رؤوسها P، وQ، وR، وS، وT، وU وأضلاع موزونة: PQ=7، PR=9، PU=14، QR=10، QS=15، RS=11، RU=2، ST=6، UT=9. استخدم خوارزمية ديكسترا لإيجاد أقصر مسار من P إلى T، مع تحديد المسار وطوله الكلي.» وتعالج إجابته هذه النقطة فقط: «تعيين تسمية دائمة 0 لـP والنظر في جيرانه: تحصل Q على قيمة عاملة 7، وR على 9، وU على 14.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 7 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحصعب7 درجاتآلة حاسبة+
• 13باستخدام جدول خوارزمية ديكسترا نفسه من السؤال السابق، حدد ترتيب حصول الرؤوس P، وQ، وR، وS، وT، وU على تسمياتها الدائمة.نمط الورقة 2سهل2 درجاتآلة حاسبة+
• 14تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «باستخدام جدول خوارزمية ديكسترا نفسه من السؤال السابق، حدد ترتيب حصول الرؤوس P، وQ، وR، وS، وT، وU على تسمياتها الدائمة.» وتعالج إجابته هذه النقطة فقط: «تحديد ترتيب التسمية الدائمة بـ P، وQ، وR، وU، وS، وT.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 2 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحسهل2 درجاتآلة حاسبة+
• 15لخمس مدن W، وX، وY، وZ، وV المسافات المباشرة التالية (كم): WX=12، WY=10، WZ=19، WV=8، XY=3، XZ=7، XV=6، YZ=2، YV=20، ZV=4. بدءاً من W، استخدم خوارزمية أقرب جار لإيجاد حد أعلى لطول جولة البائع المتجول التي تزور كل مدينة مرة واحدة وتعود إلى W.نمط الورقة 2متوسط5 درجاتآلة حاسبة+
• 16تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لخمس مدن W، وX، وY، وZ، وV المسافات المباشرة التالية (كم): WX=12، WY=10، WZ=19، WV=8، XY=3، XZ=7، XV=6، YZ=2، YV=20، ZV=4. بدءاً من W، استخدم خوارزمية أقرب جار لإيجاد حد أعلى لطول جولة البائع المتجول التي تزور كل مدينة مرة واحدة وتعود إلى W.» وتعالج إجابته هذه النقطة فقط: «من W، أقرب مدينة لم تُزر هي V (8 كم).» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 5 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحمتوسط5 درجاتآلة حاسبة+
• 17باستخدام المدن الخمس نفسها من السؤال السابق، أوجد حداً أدنى لجولة البائع المتجول بحذف المدينة W، وإيجاد الشجرة الممتدة الصغرى للمدن الأربع المتبقية، وإضافة أقصر ضلعين متصلين بـW.نمط الورقة 3 (موسّعة)صعب6 درجاتآلة حاسبة+
• 18تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «باستخدام المدن الخمس نفسها من السؤال السابق، أوجد حداً أدنى لجولة البائع المتجول بحذف المدينة W، وإيجاد الشجرة الممتدة الصغرى للمدن الأربع المتبقية، وإضافة أقصر ضلعين متصلين بـW.» وتعالج إجابته هذه النقطة فقط: «حذف W وإيجاد الشجرة الممتدة الصغرى لـX، وY، وZ، وV باستخدام خوارزمية كروسكال أو بريم.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 6 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحصعب6 درجاتآلة حاسبة+
• 19تُكوّن شبكة توصيل بياناً يجب فيه اجتياز كل ضلع مرة واحدة على الأقل، بدءاً من المستودع وانتهاءً به. الأضلاع والمسافات (كم) هي: AB=3، وBC=4، وCA=5، وCD=6، حيث A هو المستودع. رأسان بالضبط، C وD، لهما درجة فردية. أوجد طول أقصر مسار ممكن يجتاز كل ضلع مرة واحدة على الأقل ويعود إلى A.نمط الورقة 2متوسط5 درجاتآلة حاسبة+
• 20تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «تُكوّن شبكة توصيل بياناً يجب فيه اجتياز كل ضلع مرة واحدة على الأقل، بدءاً من المستودع وانتهاءً به. الأضلاع والمسافات (كم) هي: AB=3، وBC=4، وCA=5، وCD=6، حيث A هو المستودع. رأسان بالضبط، C وD، لهما درجة فردية. أوجد طول أقصر مسار ممكن يجتاز كل ضلع مرة واحدة على الأقل ويعود إلى A.» وتعالج إجابته هذه النقطة فقط: «حساب الوزن الكلي لجميع الأضلاع: 3 + 4 + 5 + 6 = 18.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 5 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحمتوسط5 درجاتآلة حاسبة+
• 21لكل من تسلسلات الدرجات التالية، حدد ما إذا كان البيان المقابل يمتلك دورة أويلرية، أم مساراً أويلرياً (وليس دورة)، أم لا هذا ولا ذاك: (أ) 4، 4، 2، 2 (كلها زوجية). (ب) 3، 3، 2، 2 (فرديتان بالضبط). (ج) 3، 3، 3، 3 (أربع فرديات).نمط الورقة 1سهل3 درجاتبدون آلة+
• 22تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لكل من تسلسلات الدرجات التالية، حدد ما إذا كان البيان المقابل يمتلك دورة أويلرية، أم مساراً أويلرياً (وليس دورة)، أم لا هذا ولا ذاك: (أ) 4، 4، 2، 2 (كلها زوجية). (ب) 3، 3، 2، 2 (فرديتان بالضبط). (ج) 3، 3، 3، 3 (أربع فرديات).» وتعالج إجابته هذه النقطة فقط: «تحديد أن (أ)، بكل رؤوسها زوجية الدرجة، تمتلك دورة أويلرية.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 3 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحسهل3 درجاتبدون آلة+
• 23اشرح لماذا تمتلك الشجرة ذات n رأساً دائماً n − 1 ضلعاً بالضبط، وحدد عدد الأضلاع في شجرة ذات 6 رؤوس.نمط الورقة 1سهل3 درجاتبدون آلة+
• 24تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «اشرح لماذا تمتلك الشجرة ذات n رأساً دائماً n − 1 ضلعاً بالضبط، وحدد عدد الأضلاع في شجرة ذات 6 رؤوس.» وتعالج إجابته هذه النقطة فقط: «شرح أن الشجرة بيان متصل بلا دورات، وأن وصل n رأساً بأقل عدد ممكن من الأضلاع مع البقاء متصلاً يتطلب n − 1 ضلعاً بالضبط.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 3 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحسهل3 درجاتبدون آلة+
• 25لبيان مثلث رؤوسه A، وB، وC، كل زوج منها موصول بضلع، ومصفوفة تجاوره M = [[0,1,1],[1,0,1],[1,1,0]]. احسب M²، واشرح ما تمثله عناصر M².نمط الورقة 2متوسط4 درجاتآلة حاسبة+
• 26تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «لبيان مثلث رؤوسه A، وB، وC، كل زوج منها موصول بضلع، ومصفوفة تجاوره M = [[0,1,1],[1,0,1],[1,1,0]]. احسب M²، واشرح ما تمثله عناصر M².» وتعالج إجابته هذه النقطة فقط: «ضرب M في نفسها للحصول على M² = [[2,1,1],[1,2,1],[1,1,2]].» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 4 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحمتوسط4 درجاتآلة حاسبة+
• 27عرّف المقصود بالدورة الهاملتونية، وأوجد دورة هاملتونية واحدة في شبكة المدن الخمس من سؤال سابق (W، وX، وY، وZ، وV، وجميع الأزواج متصلة)، مع تحديد طولها الكلي.نمط الورقة 1سهل3 درجاتآلة حاسبة+
• 28تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «عرّف المقصود بالدورة الهاملتونية، وأوجد دورة هاملتونية واحدة في شبكة المدن الخمس من سؤال سابق (W، وX، وY، وZ، وV، وجميع الأزواج متصلة)، مع تحديد طولها الكلي.» وتعالج إجابته هذه النقطة فقط: «تعريف الدورة الهاملتونية بأنها مسار مغلق يزور كل رأس من رؤوس البيان مرة واحدة بالضبط قبل العودة إلى رأس البداية.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 3 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحسهل3 درجاتآلة حاسبة+
• 29اشرح الفرق الرئيسي بين الشجرة والبيان المتصل العام، من حيث عدد الأضلاع بالنسبة لعدد الرؤوس، ومن حيث الدورات.نمط الورقة 1سهل2 درجاتبدون آلة+
• 30تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «اشرح الفرق الرئيسي بين الشجرة والبيان المتصل العام، من حيث عدد الأضلاع بالنسبة لعدد الرؤوس، ومن حيث الدورات.» وتعالج إجابته هذه النقطة فقط: «شرح أن الشجرة بيان متصل بـ n − 1 ضلعاً بالضبط وبلا دورات، بينما قد يمتلك البيان المتصل العام n − 1 ضلعاً أو أكثر ويمكن أن يحتوي دورة واحدة أو أكثر.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 2 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحسهل2 درجاتبدون آلة+
• 31تُشكّل خمسة مواقع A، وB، وC، وD، وE مربعاً ABCD طول ضلعه 1 كم (بأقطار AC = BD ≈ 1.41 كم)، إضافة إلى موقع خامس E يبعد 6.02 كم عن A وD، و5.02 كم عن B وC. بدءاً من A، تعطي خوارزمية أقرب جار الجولة A→B→C→D→E→A بطول 15.04 كم، لكن الجولة المثلى A→B→E→C→D→A طولها 13.04 كم. اشرح لماذا فشلت خوارزمية أقرب جار في إيجاد الجولة المثلى في هذه الحالة.نمط الورقة 2سهل3 درجاتبدون آلة+
• 32تحليل التصحيح: يحاول متعلم الإجابة عن المهمة الآتية: «تُشكّل خمسة مواقع A، وB، وC، وD، وE مربعاً ABCD طول ضلعه 1 كم (بأقطار AC = BD ≈ 1.41 كم)، إضافة إلى موقع خامس E يبعد 6.02 كم عن A وD، و5.02 كم عن B وC. بدءاً من A، تعطي خوارزمية أقرب جار الجولة A→B→C→D→E→A بطول 15.04 كم، لكن الجولة المثلى A→B→E→C→D→A طولها 13.04 كم. اشرح لماذا فشلت خوارزمية أقرب جار في إيجاد الجولة المثلى في هذه الحالة.» وتعالج إجابته هذه النقطة فقط: «شرح أن خوارزمية أقرب جار تتخذ الخيار الأمثل محلياً في كل خطوة دون النظر في البنية الكلية لبقية المسار.» قيّم الإجابة مقابل متطلبات المهمة الكاملة ذات 3 درجات. حدد ما يستحق درجة واذكر كل متطلب إضافي لازم للحصول على الدرجة الكاملة.تحليل تصحيحسهل3 درجاتبدون آلة+