ما هي نظرية الرسم البياني ، وكيف يتم تعريف الرسم البياني على هذا النحو؟

في عام 1736 ، بناءً على عمل عالم الفيزياء والرياضيات السويسري ليونارد أويلر (1707-1783) ، لوحظ أن سلسلة من الرؤوس تحدد ومع ذلك ، إذا كان المسار المذكور يتكون من رؤوس مختلفة دون تكرار الحواف ، فإنه يسمى مسارًا أو مسارًا أويلر. إذا وصلنا بالإضافة إلى ذلك إلى نقطة البداية ، ونعبر كل حافة مرة واحدة فقط ، فعندئذ يكون لدينا دورة أويلر (دائرة).

اقتباس (APA)

الكسندر برازة | يوليو. 2022
شهادة في الفيزياء

من جانبه ، نحدد الرسم البياني كزوج مرتب (يذهب) أين الخامس يسمي المجموعة (غير الفارغة) لجميع رؤوس أو عقد الرسم البياني ، بينما أ يحدد مجموعة (يمكن أن تكون فارغة) لجميع الحواف أو الخطوط التي تربط رؤوس الرسم البياني. عناصر المجموعة أ يمكن تعيينه كزوج غير مرتب {v، w} حيث v و w هما عناصر (عقد أو رؤوس) الخامس، بهذه الطريقة يُقال إن v و w عبارة عن رؤوس متجاورة (ترتبط بحافة).

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

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

قام أويلر بنمذجة كونيجسبيرج كرسم بياني حيث تمثل كل نقطة (قمة أو عقدة) جسرًا وكل خط (حافة) يمثل مسارًا على الأرض:

ما هو الحل لهذه المشكلة؟

لا يوجد واحد المحلول يفي بالشروط المفروضة ، لأنه ، كما أوضح أويلر ، الرؤوس ليست متساوية ، أي أن عددًا زوجيًا من الخطوط لا يؤثر على كل نقطة _[3]. لا يبدو أنه يمكننا فعل الكثير بهيكل مُعرَّف على هذا النحو ، كما هو الحال غالبًا الرياضيات، في بعض الأحيان الأمور ليست كما تبدو. وبالتالي ، فهي واحدة من أكثر المجالات غزارة ، ومستعرضة ومتعددة التخصصات _[4] المعرفة البشرية ، نظرية الرسم البياني.

الرسوم البيانية Eulerian أم مع مسار Eulerian؟

تحتوي جميع الرسوم البيانية التالية على مسارات أويلر _[5]. هل لديهم جميعًا دورات أويلر؟

لنأخذ الرسم البياني الثالث:

لنقم بترقيم القمم:

نرى بعد ذلك أن المسار المحدد بالتسلسل {3،4،6،2،1،3،7،6،5،4،2} هو مسار أويلير ، حيث يمر عبر الرسم البياني بأكمله دون تكرار الحواف ، لكنه ليس دورة أويلريان ، لأنه لا يصل إلى نقطة البداية. ماذا كان سيحدث لو قمنا بترقيم الرؤوس بشكل مختلف؟ ليس كثيرًا ، إلا أنه سيتم تحديد المسار الآن من خلال تتابع مختلف. ماذا كان سيحدث إذا اتبعنا مسارات مختلفة عن التي اقترحناها في حلنا الأولي؟ هذا السؤال أكثر تعقيدًا قليلاً للإجابة ، وهو يتضمن خوارزميات يسعدها عادةً مهندسو البرمجيات. برمجة.

للحصول على دليل أكثر صرامة لما يتم الكشف عنه هنا ، يجب أن نشير إلى النتيجة التالية:

"يكون جي رسم بياني متصل _[6]. ثم نعم جي عند دائرة كهربائية أويلر ، درجة كل رأس متساوية ، بينما إذا جي لها مسار أويلر ، G لها رأسان من الدرجة الفردية بالضبط _[7] (بالضبط القمم حيث يبدأ المسار وينتهي)".

يمكننا بعد ذلك التحقق من أنه ، في الواقع ، في الرسم البياني الذي نأخذه ، فقط الرؤوس 3 و 6 لها درجة فردية (هذا حتى لو كان ترقيم الرؤوس مختلفًا) ، لذلك فإن الرسم البياني المذكور له مسار يوليريان _[8]. بالنسبة إلى الرسوم البيانية المتبقية ، يمكننا المضي قدمًا بطريقة مماثلة والتحقق مما إذا كان لديهم بالفعل مسارات و دورات أويلريان ، أو بعبارة أخرى ، هل يمكننا رسم مثل هذه الرسوم البيانية دون التقاط قلم الرصاص والتكرار خطوط؟ يمكن استنتاج الإجابة على هذا السؤال مما تم شرحه بالفعل حتى الآن ، ومع ذلك ، فإنه يشكل تمرينًا مثيرة للاهتمام من حيث المهارات الحركية الدقيقة والإبداع والصبر ، أدعو القارئ إلى إيجاد ورسم رسوم بيانية من 6 أو أكثر القمم مع مسار أويلريان.

هل هناك أنواع أخرى من الرسوم البيانية؟ هل لنظرية الرسم البياني تطبيقات في العالم "الحقيقي"؟

هذه الرسوم البيانية التي راجعناها بإيجاز شديدة ، هي مجرد واحدة من العديد من أنواع الرسوم البيانية التي نجدها في نظرية الرسم البياني. يمكننا أيضًا العثور على رسوم بيانية مثل الأشجار ، تمثيلية للغاية في مجموعات حيث يمكن تصنيف عناصرها في التسلسلات الهرمية وفي حسابات العد و احتمالا_[9]، digraphs ، الرسوم البيانية هاميلتونيان _[10]، إلخ.

صورة لنماذج الرسوم والشبكات في نفسية. رويز ، أنا ماريا.

هذه الألغاز ، إذا أردنا تسميتها ، لها قابلية تطبيق هائلة في عالم اليوم ، في مواقف متنوعة مثل: مادة الاحياء جزيئي _[11], الحوسبة_[12]الاتصالات _[13] وتحليل الشبكة _[14]. يجدر بنا أن نسأل إذن: أليس من الغريب أن تكون مشكلة تقريبًا عاديا ستصبح واحدة من أكثر نتائج الرياضيات إثارة للاهتمام والأكثر بروزًا؟ ربما ، لهذا ، كانت مساهمة واحدة من أكثر العقول اللامعة للبشرية ضرورية.