السلام عليكم و رحمة الله و بركاته،
حل التطبيق السابق:
)
قبل تقديم مثالين على تطبيقات هذا المفهوم في المجالات المختلفة، نقدم التعريف التالي:
نفرض أن X و Y رؤوس في رسم موجه. إذا أمكنت البداية عند X ، و تتابع سلسلة من
الخطوط الموجهة (directed edges) في الاتجاهات المشار إليها على الرسم.و الانتهاء عند Y، نسمي هذه السلسلة من الخطوط الموجهة
طريق موجه من Xإلى y : (a directed path from X to Y). سوف يرمز هنا للطريق الموجه بكتابة الرؤوس الموجودة على طول هذا الطريق على التتالي.
طول الطريق الموجه يساوي عدد الخطوط الموجهة المكونة لهذا الطريق.
ملاحظة للتوضيح/
- الطريق الموجه ABC يعني أن هناك رسم موجه يحتوي على رؤوس منها A , B , c :الخط الموجه منA يمر نحو B و الرأس B يخرج منه خط موجه نحو C . هذا الطريق طوله 2 لأنه يحتوي على خطين موجهين.
أمثلة على تطبيق هذا المفهوم الرياضي في مجالات مختلفة:
مثال1/ يريد مجموعة من الآباء من مجلس المدينة تعيين اشارات مرور عند أماكن التقاطعات الخطرة في الطرق. و باعتقادهم أن أفضل طريقة لعمل ذلك: الحصول على دعم من أكثر أعضاء المجلس تأثيراً على الآخرين. و بحكم التجربة والخبرة، فإنهم يعرفون كل من يؤثر على الآخر كالتالي:
من المعلومات السابقة حدّد العضو الذي له أكبر تأثير على بقية أعضاء المجلس، و ذلك بحساب قيمة التأثير من الدرجة 1 و 2 الذي يمارسه كل عضو على أعضاء المجلس التابعين(المتأثرين)له.
الحل/
نقوم بإنشاء نموذج يمثل وضع(حالة)السيطرة الموجودة في مجموعة أعضاء المجلس. و نوع هذا النموذج: رسم موجّه.
رسم موجه يمثل وضع التأثير في المجلس
نكتب مصفوفة السقوط لهذا الرسم:
)
حيث أن المصفوفةMتعبر عن الخطوط الموجهة في النموذج (كما سبق في بداية الموضوع)
الآن نقوم بدراسة عدد الطرق الموجهة من الطول 2 ( طريق موجه يحتوي على خطين موجهين):
فنكتب المصفوفة M^2 (سنرى الآن لماذا):
لكي نفهم دلالات الأرقام في المصفوفةM^2 ، نركز على الحد(المدخل) AB للمصفوفة M^2 و الذي يساوي 2 .و كما هو موضح أعلاه فإنه يستخدم الصف A و العمود B للمصفوفة M لحساب ذلك الحد.
الشكل التالي يوضح أن الحدAB في M^2 يمثل أن هناك زوجين من الطول 2 في الرسم الموجه:
الأزواج المكونة من العدد 1 ضربت فنتج الحد AB في المصفوفة M^2 .
لاحظ أن الزوجين المكونين من العدد 1 يمثلان طريقان موجهان من الطول 2 من A إلى B ، سمّوا بـ ACB و AEB . و بذلك العدد 2 في الحدAB للمصفوفة M^2 يبين أن هناك طريقان موجهان من الطول 2 من A إلى B في الرسم الموجه.
الحد BE في المصفوفة M^2 يساوي 1 و هذا يعني أن هناك طريق موجه واحد من الطول 2 من B إلى E. تحقق من ذلك من الرسم..
مصفوفة السقوط M تمثل الرسم الموجه الذي يصور الخطوط الموجهة. و هذا يعني الطرق الموجهة من الطول 1 . و نحن الآن رأينا أن المصفوفة M^2 تحسب رقم الطرق الموجهة من الطول 2 بين كل زوج من الرؤوس. بنفس الطريقة، يمكن أن يعرض أن M^3=MMM تشير إلى رقم الطرق الموجهة من الطول 3. و بصورة عامة لدينا المبدأ التالي:
استخدام مصفوفة السقوط لحساب الطرق الموجهة من الطول n في رسم موجه/
افترض أن M مصفوفة سقوط لرسم موجه G . المصفوفة M^n تعطينا معلومات عن الطرق الموجهة من الطول n في G. على وجه التخصيص، الحد IJ من المصفوفة M^nهو رقم الطرق الموجهة من الطول n من الرأس I إلى الرأس J في الرسم الموجه G .
لنرجع الآن إلى مثال مجلس المدينة:
استخدام مصفوفة السقوط لحساب الطرق الموجهة في رسم موجه/
بدلاً من عملية عدّ الطرق الموجهة من الطول 1 أو 2 لتحديد وضع السيطرة في هذا الرسم الموجه، بامكاننا استخدام مصفوفة السقوط للحصول على نفس المعلومات و الحل يكون إذاً: تحتوي المصفوفتان M و M^2 على معلومات متعلقة بالطرق الموجهة من الطول 1 و 2في الرسم:
)
)
كمثال، عملية إضافة الحد AE لكل من M وM^2 تنتج العدد 3 الذي يعني أن هناك ثلاثة طرق موجهة من الطول 1 أو 2 من A إلى E .إن جمع حدود المصفوفة M و M^2 ينتج المصفوفة T :
)
تحسب عدد الطرق الموجهة من الطول 1 أو 2 التي تخرج بين أزواج الرؤوس في الرسم الموجه.
إذا قمنا بجمع حدود المصفوفة في كل صف، نرى أن A يمارس تأثيراً في (0+2+2+0+3+1=8) ثمان طرق و هذا العدد يمثل أكبر تأثير يمارسه أي عضو في المجلس. أي أن حل هذه المسألة هو أن العضو A له أكبر تأثير على الأعضاء من بقية الأعضاء.
إن الفائدة من هذه الطريقة لا تكمن فقط في التخلي عن أمر ممل مثل حساب الطرق الموجهة من الرسم بل أيضاً في أن نموذج المصفوفة -الممثل لهذا الرسم الموجه- يعرض إجراءات حسابية مرتبة تؤدي إلى الحصول على نفس المعلومات. و الأكثر من ذلك أن هذا النموذج يمكن إدخاله في الكمبيوتر و في آلة الرسم البياني و بذلك تجرى الحسابات في ثوان معدودة.
مثال 2/ استخدام مصفوفة السقوط لوصف انتشار مرض ما/
الرسم الموجه التالي يمثل الكيفية المحتملة لانتقال نوع من أنواع الفيروسات إلى مجموعة من العاملين في مستشفى ما. هل هناك أي من العمال يحتمل أن يكون أول من نقل المرض إلى المجموعة؟
الحل/ إذا كان المرض بدأ عن طريق هذه المجموعة فإنه من الممكن القول أنه بدأ عند شخص معين X و من ثم انتشر عند الآخرين. إذاً لابد أن يكون هناك طريق موجه من X إلى كل شخص من الآخرين(لاحظ أننا كوننا قلنا طريق موجه أي غير مباشر). بشكل أوضح، سيكون هناك طريق موجه من الطول 5 أو أقل. نبدأ الحل بتمثيل هذا الرسم بواسطة مصفوفة السقوط
)
الآن نحسب M^2,M^3,M^4,M^5 ، هذه المصفوفات تحتوي على معلومات تتعلق بالطرق الموجهة من كل من الأطوال: 2،3، 4، و 5 في الرسم الموجه.
)
)
)
)
ثم نحسب المصفوفة T :
)
في المصفوفة T،كما نرى، ليس هناك طرق موجهة من الطول 5 أو أقل من بعض الرؤوس إلى البقية. كمثال: الحد BCيساوي 0 و هذا يعني أنه ليس هناك طريق موجه من الطول 5 او أقل من BإلىC. و هذا يدل على أن المرض لم يبدأ منB و انتشر حتى C. لأن الصفين A و C هي الصفوف الوحيدة التي لا تحتوي على أصفار، فإن المرض يمكن أن يكون بدأ فقط عن طريق A أو C.
إن هذه الأمثلة التي تم نقاشها أعلاه صغيرة و بسيطة نسبياً. ففي عدة مجالات لدراسة مسائل و مشاكل حيوية حقيقية، يمكن أن يكون لمصفوفة السقوط مئات من الصفوف و الأعمدة. و هذه المسائل بالطبع تتطلب حسابات حاسوبية مطولة لإيجاد حلولها.
أسئلة للبحث:
- كيف اُخترعت هذه الطريقة؟
- ماذا أيضاً عنها؟
أرجو أن يكون مفيداً
