الرياضيات > الرياضيات
رياضة الصباح التي تسببت في إنشاء نظرية البيان
جسور كونيغسبرغ السبعة
كانت مدينة كونيغسبيرغ في القرن الثامن عشر مدينة تجارية مهمة وكانت ذات مكانة استراتيجية، وقد تميزت بأن فيها سبعة جسور وجزيرة في منتصفها.
عاش سكان تلك المدينة برخاء وراحة و كانت من عادة القاطنين فيها المشي في مدينتهم الجميلة بعد عصر أيام الأحد.
أحد السكان خطر بباله السؤال التالي: هل يمكننا أن ننظم خط سير يمكّننا من المرور على جميع مناطق المدينة وقطع جميع الجسور بحيث نقطع كل جسر مرةً واحدةً فقط؟.
وصلت هذه المسألة لعالم رياضيات مشهور هو ليونارد أويلر الذي برهن أنه بالفعل لا يمكن إيجاد مثل هذا الطريق. حيث قام أويلر بإعادة صياغة المسألة باستخدام نظرية البيان على الشكل التالي:
إذا رسمنا مناطق المدينة المختلفة على شكل رؤوس A،B،C،D و الجسور الواصلة بينها كأضلاع p،q،u،t،s،r،v
عندئذ نستطيع إيجاد مثل هذا الطريق إذا وفقط إذا استطعنا رسم الشكل (*) على ورقة دون أن نضطر لرفع القلم عن الورقة بحيث نمر بكل رأس مرة واحدة، لا أكثر ولا أقل. [ 1 ]
لنتفق على تسمية أي شكل بياني متصل يمكن رسمه بهذه الطريقة ببيان أويلري.
إذاً، لحل هذه المسألة يجب أن نتتحقق فيما اذا كان الشكل (*) بياناً أويلرياً أم لا.
قبل عرض حل أويلر لهذه المسألة لنقم أولاً بمراجعة بعض التعاريف اللازمة من نظرية البيان.
تعريف البيان ( Graph): هو مجموعة من العُقد (رؤوس) متصلة ببعضها بأقواس (أضلاع). بعض البيانات تكون موّجهة، أي تكون فيها جميع الأقواس عبارة أسهم لها اتجاه محدد.
مرتبة العقدة: عدد الأقواس التي تؤثر في تلك العقدة.
مثال: في الشكل التالي لدينا بيان غير موجه مؤلف من:
1. خمسة رؤوس: A، B، C، D و E
2. سبعة أضلاع: AB، BC، CD، DA، AE، BE، AC و BD
3. مرتبة كل من A و B تساوي 4
4. مرتبة كل من C و D تساوي 3
5. مرتبة E تساوي 2
بالعودة للمسألة المطروحة: أويلر برهن أنه إن لم يكن عدد العقد ذات المرتبة الفردية 0 أو 2 فإن ذلك البيان لا يمكن أن يكون بياناً أويلرياً. ومنه بالعودة للشكل (*)
نستطيع أن نرى أن مرتبة كل من ِ A،B،D هي 3، ومرتبة C هي 5. أي أن عدد العقد ذات المرتبة الفردية هو 4 ومنه نستنتج أن الشكل (*) لا يمكن أن يكون بياناً أويلرياً وبالتالي لا يمكن ايجاد طريق يربط مناطق المدينة بحيث يمر من كل جسر مرة واحدة فقط.
تمرين لتثبيت الفكرة:
أي من الأشكال التالية هو بيان أويلري؟
مسائل ترتبط بنظرية البيان:
مسألة ساعي البريد:
لنفترض أن ساعي البريد يريد أن ينتقل بين عدة مدن ليوصل البريد ويريد أن يعرف ماهو أقصر طريق يمكنه أن يسلك على الرغم من أننا نعلم المسافة الفاصلة بين المدن تبقى هذه المسألة من أكثر المسائل تعقيداً في الرياضيات، ما يمكننا فعله هو حساب طول جميع الطرق التي يمكن أن يسلكها ليصل لجميع المدن ومن ثم نقارن. ولكن هل تعلم أنه لو أراد أن يمر على 10 مدن فقط فإن عدد الطرق الممكنة لترتيب هذه المدن هو 10! = 3،628،800 طريق. فلو أراد جمع أطوال تلك الطرق لقضى وقتاً أطول من أي من الطرق التي يمكن أن يسلكها. تخيّل أنه يريد أن يمر على 100 مدينة. فظيع أليس كذلك؟!
إن على شركات الطيران أن تفكر بربط مئات المدن والمطارات وبأقصر طريقة ممكنة لذا فإن هذه المسألة هي من المسائل التي وُضع لها خوارزميات للحل ويمكن للقارئ العودة لبعض المراجع التي تناولت هذا الموضوع.
مسألة تلوين الخرائط بأربعة ألوان:
نريد تلوين خريطة للبلدان بحيث أن يختلف لونا كل بلدين متجاورين. ما هو أكبر عدد من الألوان اللازم للقيام بذلك؟
حاشية:
[1]- مثل هذا المسار يسمى مساراً أويلرياً.
المصطلحات العلمية المستعملة:
بيان Graph
رؤوس / عقد vertices
أضلاع edges
مسار أويلري Eulerian path / Euler walk
مرتبة degree
المصادر