نظرية التخطيط البياني Graph Theory

سنحكي اليوم قصة عالم رياضيات نمساوي اسمه Leonhard Eular  كان السبب بعد إرادة الله سبحانه، في اختراع نظرية اسمها Graph Theory في أوائل القرن الثامن عشر، اخترع هذه النظرية لإيجاد حل للمشكلة التي واجهته حينما زار مدينة Königsberg في ألمانيا، هذه المدينة يخترقها نهر river عليه جزيرتين صغيرتين Island1 & Island2. ترتبط هاتان الجزيرتان بضفتي النهر  Riverbank1 & Riverbank2 وببعضهما البعض عن طريق سبعة من الجسور Bridges، كما توضح الصورة التالية:

أراد هذا العالم التجول في إرجاء هذه المدينة بكاملها بدون المرور على جسر أكثر من مرة!
لدراسة إمكانية ذلك؛ قام العالم برسم خريطة توضيحية بسيطة للمدينة، مثّل فيها الجهات التي يريد التنقل فيما بينها (كلاً من Is1, Is2, rb1 and rb2)  كنقاط أو أطراف nodes، ثم مثَّل فيها كل جسر كوصلة link تربط بين هذه الأطراف كما هي موجودة في أرض الواقع، هذا التمثيل سمِّيَ Graph أو تمثيل بياني:
-حيث أن Is= Island, rb= Riverbank and b=bridge-

بعد ذلك أوجد مفهوم جديد يسمى Degree of the Node of the Graph أو درجة الطرف في التخطيط، حيث أن لكل طرف درجة هذه الدرجة هي عدد الوصلات التي تصل هذا الطرف مع الأطراف الأخرى المجاورة له، أي عدد الـlinks الداخلة أو الخارجة من هذا الطرف، من الممكن أن يكون هذا العدد فردي أو زوجي بطبيعة الحال.
 لنوجد معاً درجة كل طرف في التخطيط:

توصل بعد ذلك إلى النظرية التي تقول:
يمكنك حل المشكلة والمشي في أرجاء المدينة مع العبور على كل جسر مرة واحدة فقط في حالتين:

عدا ذلك فإن المشكلة مستحيلة الحل ولا يمكنك المشي في أرجاء المدينة دون العبور على أحد الجسور أكثر من مرة!

ثم حدد مسار السير في الحالات التي يمكن حل المشكلة فيها، كالتالي:

• إذا كان لديك طرفين من درجة فردية، فإن السير سيبدأ من الطرف ذو الدرجة الفردية الأول، وينتهي عند الطرف ذو الدرجة الفردية الثاني.
• إذا لم يكن لديك ولا طرف من درجة فردية، بمعنى أن كل الأطراف من درجة زوجية، فإن المشي سيبدأ من أحد هذه الأطراف وينتهي عند نفس الطرف!

ثم أقرّ بأنه لا يمكنه التجوال في أرجاء مدينة Königsberg بدون العبور على جسر أكثر من مرة، لأنه يوجد أربعة أطراف من درجة فردية في graph هذه المدينة!!

-=-=-=-=-=-=-

عرفت هذه المشكلة باسم "Bridge of Königsberg problem" ومؤخراً أصبحت معروفة باسم العالم: "Finding an Eular path through a graph"، وهي تعتبر حجر الأساس وأول نظرية في عالم الـGraph.

وهذا يقودنا للسؤال: ما معنة كلمة Graph؟!

الـGraph كما رأينا هو مجموعة من الأطراف nodes تربط ما بينهما مجموعة من الوصلات links، من الممكن أن نعتبر كل طرف يمثّل حالة، وللإنتقال من حالة إلى أخرى نستخدم الوصلة التي تصل بينهما.
يفيد تمثيل المشاكل بهذه الطريقة في اختزال واحتواء المشكلة، وزيادة فهمها مما يسهل الطريق إلى حلها، كما تعتبرGraph Theory أفضل أداة للتعليل reasoning في أي تركيب structure يحوي مجموعة من الكائنات objects بينهما مجموعة من العلاقات relations.
في علوم الذكاء الاصطناعي، تستخدم هذه النظرية في تقنيات البحث وخصوصاً في State-space search بنوعيها Depth-first and Breadth-first.

والآن بعد أن انتهينا من سرد القصة وتعرفنا على النظرية كاملة، ما رأيكم بمثال آخر نطبّق النظرية عليه ونرى هل يمكننا حل مشكلته أم لا؟!

إليكم هذه الخريطة:

أول خطوة، نمثلها كـGraph:

ثم نوجد درجة كل node فيها:

ثم نحدد عدد الأطراف من الدرجة الفردية، يوجد لدينا طرفين من درجة فردية.
إذن المشكلة ممكنة الحل والمشي بدون العبور أكثر من مرة على كل جسر ممكن.
لنحدد معاً مسار المشي الذي لابد من أن يبدأ من أحد الأطراف ذات الدرجة الفردية (Is1 or rb1)  وينتهي عند الطرف الآخر، من الممكن أن يكون أحد المسارات التالية:

1. Is1(through b5) --> rb2(b6) --> Is1(b2) --> rb1(b3) --> Is1(b1) --> Is2(b4) --> rb1

2. Is1(b1) --> Is2(b4) --> rb1(b3) --> Is1(b5) --> rb2(b6)--> Is1(b2) --> rb1

3. Is1(b2) --> rb1(b3) --> Is1(b5) --> rb2(b6) --> Is1(b1) --> Is2(b4) --> rb1

4. rb1(b2) --> Is1(b5) --> rb2(b6) --> Is1(b3) --> rb1(b4) --> Is2(b1) --> Is1

5. rb1(b4) --> Is2(b1) --> Is1(b5) --> rb2(b6) --> Is1(b2) --> rb1(b3) --> Is1
           .
           .
           . وهكذا :)

-=-=-=-=-=-=-

إليك مثال آخر:

يبدو أن مشكلته ممكنة الحل، هل يمكنك حلها؟! نعم أنا واثقة من ذلك، طبّق الدرس عليها مباشرة وأوجد المسارات، ستجد أن كل مسار يبدأ وينتهي في نفس الطرف node.

-=-=-=-=-=-=-

أرجو عزيزي القارئ أن يكون هذا الدرس قد أعطاك طريقة ذكية لحل مشكلات التنقل أثناء النظر إلى أي خريطة في حياتك اليومية، كما أرجو أن يكون قد وضع أقدامك على نقطة البداية في دراسة أساليب البحث في برامج الذكاء الاصطناعي.. والسلام عليكم

1

الاقسام الرئيسية

القائمة البريدية

  فضائح | ماسنجر | تداول | الحياة الزوجية | عجائب وغرائب| دروس تعليمية | عالم حواء | فضائح الفن | ستار اكاديمي | نكت | برامج | صور | | شات سعودي | شات عربي | ماسينجر | مسجات | دليل مواقع | دليلك | مواقع سعودية | مواقع كويتية | مواقع بحرينية | مواقع قطرية | مواقع عمانية | مواقع يمنية | مواقع عراقية | مواقع اماراتية | دردشة خليجية | دردشة سعودية | دردشة عربية | شات صوتي | دردشة صوتية | دردشة كويتية | دردشة اماراتية | دردشة عمانية | دردشة قطرية | دردشة بحرينية | دردشة عراقية | دردشة يمنية | سكس | طريق الاسلام, انا مسلم , طريق الهدايه , مسلمون , منوعات اسلاميه | اسلاميات , برامج اسلامية , منوعات اسلامية | جنس | الاسرة المسلمة , الاسرة العربية , اسرتي , عائلتي | برامج الاسره , نصائح معلومات , اسرة عربية سعودية خليجية | دروس تعليمية , مكتبة الدروس التعليمية | شروح برامج , شرح برامج , دورات تعليميه | طب وصحه - المركز الطبي | طبيبك على الانترنت , معلومات طبية , معلومات صحيه