تطبيقات نظرية الرسم البياني
الرسوم البيانية المستوية
يقال أن الرسم البياني G يكون مستويًا إذا كان يمكن تمثيله على مستوى بطريقة تجعل القمم كلها نقاطًا مميزة ، والحواف منحنيات بسيطة ، ولا تلتقي حافتان ببعضهما البعض إلا في أطرافها. على سبيل المثال ، K 4 ، الرسم البياني الكامل على أربعة قمم ، هو مستوي ، كما يوضح الشكل 4A.
يقال أن هناك رسمان بيانيان متجانسان إذا كان يمكن الحصول على كليهما من نفس الرسم البياني من خلال التقسيمات الفرعية للحواف. على سبيل المثال ، الرسوم البيانية في الشكل 4 أ والشكل 4 ب متجانسة.
الرسم البياني K m، n هو رسم بياني يمكن من خلاله تقسيم مجموعة القمة إلى مجموعتين فرعيتين ، إحداهما برؤوس m والأخرى برقم n. أي رأسين من نفس المجموعة الفرعية غير متجاورتين ، في حين أن أي رأسين من مجموعات فرعية مختلفة متجاورة. أثبت عالم الرياضيات البولندي Kazimierz Kuratowski في عام 1930 النظرية الشهيرة التالية:
من الشروط الضرورية والكافية لرسم G أن يكون مستويًا هو أنه لا يحتوي على رسم فرعي متماثل إلى K 5 أو K 3،3 كما هو موضح في الشكل 5.
الانكماش الأولي للرسم البياني G هو تحويل G إلى رسم بياني جديد G 1 ، بحيث يتم استبدال ذروتين متجاورتين u و υ من G برأس جديد w في G 1 و w متجاور في G 1 إلى جميع القمم إلى الذي يكون إما u أو adj مجاورًا في G. يقال أن الرسم البياني G * هو انكماش لـ G إذا كان يمكن الحصول على G * من G بواسطة سلسلة من التقلصات الأولية. فيما يلي توصيف آخر للرسم البياني المستوي بسبب عالم الرياضيات الألماني K. Wagner في عام 1937.
الرسم البياني مستوٍ إذا وفقط إذا لم يكن قابلاً للانكماش إلى K 5 أو K 3،3.
مشكلة خريطة الألوان الأربعة
لأكثر من قرن من الزمان ، كان حل مشكلة الخريطة الأربعة الألوان مستعصيا على كل محلل حاول ذلك. ربما جذبت المشكلة انتباه موبيوس ، لكن أول إشارة مكتوبة إليها تبدو أنها رسالة من أحد فرانسيس جوثري إلى شقيقه ، طالب أوغستوس دي مورغان ، في عام 1852.
تتعلق المشكلة بالخرائط المستوية - أي التقسيمات الفرعية للطائرة إلى مناطق غير متداخلة يحدها منحنيات بسيطة مغلقة. في الخرائط الجغرافية لوحظ تجريبيًا ، في العديد من الحالات الخاصة التي تمت تجربتها ، أنه على الأكثر ، هناك حاجة إلى أربعة ألوان لتلوين المناطق بحيث يتم دائمًا تلوين منطقتين تشتركان في حد مشترك بشكل مختلف ، وفي بعض الحالات التي تكون ضرورية على الأقل أربعة ألوان. (لا تعتبر المناطق التي تلتقي عند نقطة معينة فقط ، مثل ولايتي كولورادو وأريزونا في الولايات المتحدة ، حدود مشتركة). يشكل إضفاء الطابع الرسمي على هذه الملاحظة التجريبية ما يسمى "نظرية الألوان الأربعة". تكمن المشكلة في إثبات أو دحض التأكيد على أن هذا هو الحال لكل خريطة مستوية. من السهل إثبات أن الألوان الثلاثة لن تكون كافية ، في حين تم إثبات كفاية خمسة ألوان في عام 1890 من قبل عالم الرياضيات البريطاني PJ Heawood.
في عام 1879 ، اقترح رجل اللغة الإنجليزية AB Kempe حلًا لمشكلة الألوان الأربعة. على الرغم من أن Heawood أظهر أن حجة Kempe كانت معيبة ، فقد أثبت اثنان من مفاهيمها أنها مثمرة في التحقيق اللاحق. واحدة من هذه ، تسمى عدم التفادي ، تنص بشكل صحيح على استحالة إنشاء خريطة يكون فيها كل واحد من التكوينات الأربعة غائبًا (تتكون هذه التكوينات من منطقة مع جارين ، واحد مع ثلاثة ، واحد مع أربعة ، وواحد مع خمسة). المفهوم الثاني ، وهو مفهوم الاختزال ، يأخذ اسمه من دليل Kempe الصحيح أنه إذا كانت هناك خريطة تتطلب خمسة ألوان على الأقل وتحتوي على منطقة بها أربعة (أو ثلاثة أو اثنين) ، فيجب أن تكون هناك خريطة تتطلب خمسة ألوان لعدد أقل من المناطق. كانت محاولة كيمبي لإثبات قابلية تصغير خريطة تحتوي على منطقة بها خمسة جيران خاطئة ، ولكن تم تصحيحها في دليل نشر في عام 1976 من قبل كينيث أبيل و فولفجانج هاكن من الولايات المتحدة. اجتذب برهانهم بعض الانتقادات لأنه استلزم تقييم 1،936 حالة مميزة ، تضم كل منها ما يصل إلى 500،000 عملية منطقية. ابتكر Appel و Haken والمتعاونون معهم برامج جعلت من الممكن لجهاز كمبيوتر رقمي كبير التعامل مع هذه التفاصيل. احتاج الكمبيوتر إلى أكثر من 1000 ساعة لأداء المهمة ، ويتكون الدليل الرسمي الناتج من عدة مئات من الصفحات.
دورات أويلريان ومشكلة جسر كونيغسبرغ
يتكون Multigraph G من مجموعة V (G) غير فارغة من القمم ومجموعة فرعية E (G) من مجموعة أزواج غير مرتبة من عناصر مميزة من V (G) بتردد f ≥ 1 مرتبط بكل زوج. إذا كان الزوج (x 1 ، x 2) بتردد f ينتمي إلى E (G) ، فإن القمم x 1 و x 2 يتم ربطها بحواف f.
دورة أويلريان لخط متعدد G هي سلسلة مغلقة تظهر فيها كل حافة مرة واحدة بالضبط. أظهر أويلر أن الرسم المتعدد يمتلك دورة أويلريان إذا وفقط إذا كان متصلاً (بصرف النظر عن النقاط المعزولة) وأن عدد رؤوس الدرجة الفردية إما صفر أو اثنين.
نشأت هذه المشكلة أولاً بالطريقة التالية. نهر بريجل ، الذي يتكون من التقاء فرعيه ، يمر عبر بلدة كونيغسبرغ ويتدفق على جانبي جزيرة كنييبهوف. كان هناك سبعة جسور ، كما هو مبين في الشكل 6 أ. تساءل سكان البلدة عما إذا كان من الممكن الذهاب للمشي وعبور كل جسر مرة ومرة فقط. هذا يعادل إيجاد دورة أويلريان للخط المتعدد في الشكل 6 ب. أوضح أويلر أن ذلك مستحيل لأن هناك أربعة قمم لترتيب فردي.
