مقالات

5.S: نظرية الرسم البياني (ملخص)


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

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

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

  • هل يمكن رسم الرسم البياني في المستوى بدون تقاطع الحواف؟ إذا كان الأمر كذلك ، فما عدد المناطق التي يقسمها هذا الرسم المستوى إليها؟
  • هل من الممكن تلوين رؤوس الرسم البياني بحيث يكون للرؤوس ذات الصلة ألوان مختلفة باستخدام عدد قليل من الألوان؟ كم عدد الألوان المطلوبة؟
  • هل من الممكن تتبع كل حافة الرسم البياني مرة واحدة بالضبط دون رفع قلمك الرصاص؟ ما هي أنواع "المسارات" الأخرى التي قد يمتلكها الرسم البياني؟
  • هل يمكنك العثور على رسوم بيانية فرعية بخصائص معينة؟ على سبيل المثال ، متى يحتوي الرسم البياني (ثنائي الأجزاء) على رسم بياني فرعي ترتبط فيه جميع الرؤوس برأس واحد آخر فقط؟

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

مراجعة الفصل

1

أي الرسوم البيانية أدناه (إن وجدت) متطابقة؟ أيهما مختلف؟ يشرح.

المحلول

الرسمان البيانيان الأول والثالث متماثلان (حاول سحب الرؤوس حولها لجعل الصور متطابقة) ، لكن الرسم البياني الأوسط مختلف (والذي يمكنك رؤيته ، على سبيل المثال ، من خلال ملاحظة أن الرسم البياني الأوسط له رأس واحد فقط من الدرجة 2 ، في حين أن الآخرين لديهم رأسان من هذا القبيل).


شاهد الفيديو: مادة الاقتصاد. شرح نظرية الانتاج و حل السؤال الواجب. شرح الدكتور (شهر اكتوبر 2021).