TechCodeview

يقال إن الرسم البياني مستو إذا كان من الممكن رسمه في مستوى بحيث لا تتقاطع حوافه.

مثال: الرسم البياني الموضح في الشكل هو رسم بياني مستو.

مُهيئ القاموس C#

منطقة الرسم البياني: ضع في اعتبارك رسمًا بيانيًا مستوًا G=(V,E).يتم تعريف المنطقة على أنها مساحة من المستوى تحدها حواف ولا يمكن تقسيمها بشكل أكبر. يقسم الرسم البياني المستوي الخطط إلى منطقة واحدة أو أكثر. واحدة من هذه المناطق ستكون لا نهائية.

منطقة محدودة: إذا كانت مساحة المنطقة محدودة، فإن تلك المنطقة تسمى منطقة محدودة.

المنطقة اللانهائية: إذا كانت مساحة المنطقة لا نهائية، تسمى تلك المنطقة منطقة لا نهائية. يحتوي الرسم البياني المستوي على منطقة واحدة لا نهائية فقط.

مثال: خذ بعين الاعتبار الرسم البياني الموضح في الشكل. حدد عدد المناطق والمناطق المحدودة والمنطقة اللانهائية.

حل: هناك خمس مناطق في الرسم البياني أعلاه، أي ص₁، ص₂، ص₃، ص₄، ص₅.

هناك أربع مناطق محدودة في الرسم البياني، أي ص₂، ص₃، ص₄، ص₅.

هناك منطقة محدودة واحدة فقط، أي ص₁

خصائص الرسوم البيانية المستوية:

1. إذا كان الرسم البياني المستوي المتصل G يحتوي على حواف e ومناطق r، فإن r ≦ إنها.
2. إذا كان الرسم البياني المستوي المتصل G يحتوي على حواف e ورؤوس v ومناطق r، فإن v-e+r=2.
3. إذا كان الرسم البياني المستوي المتصل G له حواف e ورؤوس v، فإن 3v-e≧6.
4. رسم بياني كامل K_نهو مستو إذا وفقط إذا ن<5.< li>
5. رسم بياني ثنائي كامل K_مليونيكون مستويًا إذا وفقط إذا كان m3.

مثال: أثبت أن الرسم البياني الكامل K₄مستو.

حل: الرسم البياني الكامل K₄يحتوي على 4 رؤوس و 6 حواف.

نحن نعلم أنه بالنسبة للرسم البياني المستوي المتصل 3v-e≧6. ومن ثم بالنسبة لـ K₄، لدينا 3x4-6=6 مما يحقق الخاصية (3).

بيثون rstrip

وهكذا ك₄هو رسم بياني مستو. ومن ثم ثبت.

الرسم البياني غير المستوي:

يقال إن الرسم البياني غير مستو إذا لم يكن من الممكن رسمه في مستوى بحيث لا تتقاطع حوافه.

مثال: الرسوم البيانية الموضحة في الشكل هي رسوم بيانية غير مستوية.

لا يمكن رسم هذه الرسوم البيانية في مستوى بحيث لا تتقاطع أي حواف، وبالتالي فهي رسوم بيانية غير مستوية.

خصائص الرسوم البيانية غير المستوية:

يكون الرسم البياني غير مستوي إذا وفقط إذا كان يحتوي على رسم بياني فرعي متماثل لـ K₅أو ك_3.3

تي الوجه بالتخبط

مثال 1: أظهر أن ك₅غير مستو.

حل: الرسم البياني الكامل K₅يحتوي على 5 رؤوس و10 حواف.

الآن، للحصول على رسم بياني مستو متصل 3v-e≧6.

وبالتالي بالنسبة لـ K₅، لدينا 3 × 5-10=5 (وهو ما لا يحقق الخاصية 3 لأنه يجب أن يكون أكبر من أو يساوي 6).

وهكذا، ك₅هو رسم بياني غير مستو.

مثال 2: أظهر أن الرسوم البيانية الموضحة في الشكل غير مستوية من خلال إيجاد رسم بياني فرعي متماثل لـ K₅أو ك_3.3.

حل: إذا قمنا بإزالة الحواف (V₁،في₄)،(في₃،في₄) و (ف₅،في₄) الرسم البياني G₁، يصبح متجانسًا لـ K₅.وبالتالي فهو غير مستو.

إذا قمنا بإزالة الحافة V_{2، الخامس}7) الرسم البياني ز₂يصبح متجانسًا لـ K_3.3.وبالتالي فهو غير مستو.

تلوين الرسم البياني:

لنفترض أن G= (V,E) عبارة عن رسم بياني بدون حواف متعددة. تلوين قمة G هو تعيين الألوان لرؤوس G بحيث يكون للرؤوس المجاورة ألوان مختلفة. الرسم البياني G يكون M-Colorable إذا كان هناك تلوين G الذي يستخدم M-Colors.

التلوين المناسب: يكون التلوين صحيحًا إذا كان أي رأسين متجاورين u و v لهما ألوان مختلفة وإلا فإنه يسمى تلوينًا غير مناسب.

مثال: خذ بعين الاعتبار الرسم البياني التالي واللون C={r, w, b, y}. قم بتلوين الرسم البياني بشكل صحيح باستخدام جميع الألوان أو ألوان أقل.

الرسم البياني الموضح في الشكل هو الحد الأدنى 3 قابل للتلوين، وبالتالي x(G)=3

حل: يوضح الشكل الرسم البياني ملونًا بشكل صحيح بجميع الألوان الأربعة.

يوضح الشكل الرسم البياني ملونًا بشكل صحيح بثلاثة ألوان.

عدد لوني G: يُطلق على الحد الأدنى لعدد الألوان اللازمة لإنتاج تلوين مناسب للرسم البياني G العدد اللوني لـ G ويُشار إليه بـ x(G).

int إلى سلسلة Java

مثال: العدد اللوني لـ K_نهو ن.

حل: تلوين K_نيمكن إنشاؤها باستخدام ألوان n عن طريق تعيين ألوان مختلفة لكل قمة. لا يمكن تعيين نفس اللون لرأسين، حيث أن كل رأسين في هذا الرسم البياني متجاوران. ومن هنا العدد اللوني لـ K_ن= ن.

تطبيقات تلوين الرسم البياني

تتضمن بعض تطبيقات تلوين الرسم البياني ما يلي:

• تسجيل التخصيص
• تلوين الخريطة
• فحص الرسم البياني الثنائي
• تخصيص ترددات الراديو المحمول
• عمل جدول زمني وما إلى ذلك.

الدولة وإثبات نظرية المصافحة.

نظرية المصافحة: مجموع درجات جميع القمم في الرسم البياني G يساوي ضعف عدد الحواف في الرسم البياني.

رياضيا يمكن القول على النحو التالي:

∑_v∈Vدرجة (الخامس) = 2ه

دليل: دع G = (V, E) يكون رسمًا بيانيًا حيث V = {v₁،في₂، . . . . . . . . . .} تكون مجموعة القمم و E = {e₁،إنها₂. . . . . . . . . .} تكون مجموعة الحواف. نحن نعلم أن كل حافة تقع بين رأسين، لذا فهي توفر درجة واحدة لكل رأس. ومن ثم تساهم كل حافة بالدرجة الثانية للرسم البياني. لذا فإن مجموع درجات جميع القمم يساوي ضعف عدد الحواف في G.

وبالتالي، ∑_v∈Vدرجة (الخامس) = 2ه

قائمة الأديان