تغيير اللغة

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

سجّل الدخول إلى Mathigon

أو

حساب جديد     إعادة تعيين كلمة المرور     

الرسوم البيانية والشبكات
مقدمة
جسور كونيجسبيرج
المصافحة والتعارف
مخططات مستوية
تلوين الخريطة
مشكلة البائع المتجول
مشاكل الجدولة
الرسوم البيانية في الحياة اليومية

شارك

إعادة تعيين التقدم

سيؤدي هذا إلى حذف تقدمك وبيانات الدردشة لجميع الفصول في هذه الدورة التدريبية ، ولا يمكن التراجع عنها!

قائمة المصطلحات

حدد واحدة من الكلمات الرئيسية على اليسار ...

الرسوم البيانية والشبكاتجسور كونيجسبيرج

وقت القراءة: ~20 min

كان أول علماء الرياضيات الذين يفكرون في الرسوم البيانية والشبكات ليونارد أويلر. كانت أويلر مفتونة بمشكلة قديمة تتعلق ببلدة كونيجسبيرج بالقرب من بحر البلطيق.

يقسم نهر بريجل كونيغسبرغ إلى أربعة أجزاء منفصلة ، متصلة ببعضها بواسطة سبعة جسور. هل من الممكن التجول في المدينة عبور جميع الجسور مرة واحدة بالضبط - ولكن ليس أكثر من مرة؟ (يمكنك البدء والانتهاء في أي مكان ، وليس بالضرورة في نفس المكان.)

حاول العثور على مسار صالح من خلال الرسم على هذه الخرائط:

جريطة 1

جريطة 2

جريطة 3

جريطة 4

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

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

أصبحت مشكلة "التجول في مدينة أثناء عبور كل جسر مرة واحدة بالضبط" مشكلة "رسم رسم بياني بضربة واحدة مستمرة مع تتبع كل حافة مرة واحدة بالضبط".

على الورق ، ضع بعض الرسوم البيانية المختلفة ثم حاول تحديد أي منها يمكن رسمه بضربة واحدة مستمرة.

تمامًا مثل خرائط المدينة من قبل ، نجد أن بعض الرسوم البيانية ممكنة بينما البعض الآخر ليس كذلك. لمساعدتنا على فهم السبب ، دعنا نصنف كل روؤس درجة. ثم يمكننا تلوين الروؤس بطرق مختلفة ، ومحاولة الكشف عن نمط:

القيمة
الحجم
الأعداد الأولية
زوجي و فردى

هذه الرسوم البيانية ممكنة

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

هذه الرسوم البيانية ليست ممكنة

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

بمقارنة هذه الأرقام بالرسوم البيانية الممكنة والأخرى غير الممكنة ، يبدو أنه يمكن رسم الرسم البياني إذا كان . يمكن تفسير هذا الشرط إذا نظرنا إلى قمة واحدة فقط في الرسم البياني:

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

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

Archie