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

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

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

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

في ما يلي لغز آخر يتعلق بنظرية الرسم البياني. يوجد في قرية صغيرة ثلاثة منازل وثلاثة مصانع مرافق تنتج الماء والكهرباء والغاز. يجب أن نربط كل من الدورات التدريبية بكل من محطات المرافق ، ولكن نظرًا لتصميم القرية ، لا يُسمح بالعبور للأنابيب والكابلات المختلفة.

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

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

K3 مستوي.

K4 .

K5 .

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

مستوي

هذا رسم بياني مستوي لكن ${n} الرؤوس مجطلطين. إعادة ترتيب الرؤوس بحيث لا تتداخل أي من الحواف.

صيغة أويلر

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

رؤوس
وجوه
حواف
11 رؤوس + وجوه

رؤوس
وجوه
حواف
15 رؤوس + وجوه

رؤوس
وجوه
حواف
25 رؤوس + وجوه

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

FVE
010

0 + 1  =  0 + 1

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

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

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

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

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

Icosahedron
20 وجوه
12 رؤوس
30 حواف

Rhombicosidodecahedron
62 الوجوه
60 رؤوس
120 حواف

Truncated Icosahedron
32 وجوه (12 أسود ، 20 أبيض)
60 رؤوس
90 حواف