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

حاول توصيل كل منزل بكل شركة من شركات المرافق أدناه ، دون تقاطع أي من خطوطك:

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

الرسم البياني الكامل K5 هو أصغر رسم بياني ليس مستويًا. أي رسم بياني آخر يحتوي على K5 كخط رسم فرعي بطريقة ما ليس مستويًا أيضًا. يتضمن هذا K6 و K7 وجميع الرسوم البيانية الكاملة الكبيرة. الرسم البياني في أحجية المرافق الثلاث هو الرسم البياني الثنائي K3,3. اتضح أن أي رسم بياني غير مستوي يجب أن يحتوي إما على K5 أو K3,3 (أو قسم فرعي من هذين الرسمين البيانيين) كرسم فرعي. وهذا ما يسمى نظرية كوراتوفسكي.

صيغة أويلر

جميع الرسوم البيانية المستوية تقسم الطائرة التي يتم رسمها إلى عدد من المناطق ، تسمى الوجه.

عند مقارنة هذه الأرقام ، ستلاحظ أن عدد الحواف يكون دائمًا واحد أقلأكبرنفس الشيء من عدد الوجوه بالإضافة إلى عدد القمم. بعبارة أخرى ، F + V = E + 1. تسمى هذه النتيجة معادلة أويلر وسميت باسم نفس عالم الرياضيات الذي حل مشكلة جسور كونيجسبيرج. لسوء الحظ ، هناك عدد لا نهائي من الرسوم البيانية ولا يمكننا التحقق من كل واحد لمعرفة ما إذا كانت معادلة أويلر تعمل. بدلاً من ذلك ، يمكننا محاولة العثور على إثبات بسيط يعمل مع أي رسم بياني ...

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

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

هذا يعني أننا يمكن استخدام صيغة أويلر ليس فقط للرسوم البيانية المستوية ولكن أيضًا لجميع الأشكال المتعددة الوجوه - مع اختلاف بسيط واحد. عند تحويل متعدد الوجوه إلى رسوم بيانية ، يختفي أحد الوجوه: يصبح الوجه العلوي متعدد الوجوه هو "الخارج" ؛ من الرسوم البيانية. بمعنى آخر ، إذا حسبت عدد حواف و وجهًا و رؤوس من أي متعدد الوجوه ، ستجد أن F + V = E + .