المخطط الموجَّه وحل المسائل بالمخططات

هذه الورشة إضافية وليست في الكتب السورية. المخطط نموذج بسيط: الرؤوس أشخاص أو مدن أو فرق، والأضلاع علاقات (صداقة، طريق، مباراة). وإذا كان للعلاقة اتجاه («أ سبق ب») رسمنا الضلع بسهم فيصير المخطط موجَّهًا. لكل رأس عدد من الأسهم الخارجة وعدد من الأسهم الداخلة.

من المسائل الكلاسيكية: المصافحة في مجموعة من n شخصًا (كل شخص يصافح كل شخص مرة واحدة) ومباريات الدوري (كل فريق يلعب مع كل فريق آخر). مجموع درجات الرؤوس يساوي ضعف عدد الأضلاع، فعدد الأضلاع نصف مجموع الدرجات. وإذا اتصلت n رؤوس كلها ببعضها كان عدد الأضلاع n·(n − ١) ÷ ٢.

الخطأ الشائع أن نعدّ كل ضلع مرتين. وخطأ آخر أن نخلط بين الأسهم الخارجة والداخلة. ونحلّ مسألة الطريق بعدّ أضلاع أقصر مسار.