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

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

مثال على تلوين الرسم البياني

جافا عدد صحيح

في هذا الرسم البياني، نعرض الرسم البياني الملون بشكل صحيح، والذي يتم وصفه على النحو التالي:

يحتوي الرسم البياني أعلاه على بعض النقاط، والتي نوضحها على النحو التالي:

• لا يمكن استخدام نفس اللون لتلوين الرأسين المتجاورين.
• ومن ثم، يمكننا أن نسميه رسمًا بيانيًا ملونًا بشكل صحيح.

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

هناك تطبيقات مختلفة لتلوين الرسم البياني. وفيما يلي وصف لبعض تطبيقاتها الهامة:

• تكليف
• تلوين الخريطة
• جدولة المهام
• سودوكو
• إعداد الجدول الزمني
• حل الصراع

رقم لوني

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

مثال على الرقم اللوني:

لفهم الرقم اللوني، سننظر إلى الرسم البياني، والذي يتم وصفه على النحو التالي:

يحتوي الرسم البياني أعلاه على بعض النقاط، والتي نوضحها على النحو التالي:

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

أنواع العدد اللوني للرسوم البيانية:

هناك أنواع مختلفة من الأعداد اللونية للرسوم البيانية، والتي يتم وصفها على النحو التالي:

الرسم البياني للدورة:

يُعرف الرسم البياني باسم الرسم البياني الدائري إذا كان يحتوي على حواف 'n' ورؤوس 'n' (n >= 3)، والتي تشكل دورة بطول 'n'. يمكن أن يكون هناك فقط 2 أو 3 درجات لجميع القمم في الرسم البياني للدورة.

رقم لوني:

1. سيكون الرقم اللوني في الرسم البياني الدائري هو 2 إذا كان عدد القمم في هذا الرسم البياني زوجيًا.
2. سيكون الرقم اللوني في الرسم البياني الدائري هو 3 إذا كان عدد القمم في هذا الرسم البياني فرديًا.

أمثلة على الرسم البياني للدورة:

هناك أمثلة مختلفة للرسوم البيانية للدورة. يتم وصف بعضها على النحو التالي:

مثال 1: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

حل: في الرسم البياني للدورة أعلاه، هناك 3 ألوان مختلفة لثلاثة رؤوس، ولم يتم تلوين أي من القمم المجاورة بنفس اللون. في هذا الرسم البياني، عدد الرءوس فردي. لذا

الرقم اللوني = 3

مثال 2: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

حل: في الرسم البياني للدورة أعلاه، يوجد لونان لأربعة رؤوس، ولم يتم تلوين أي من القمم المجاورة بنفس اللون. في هذا الرسم البياني، عدد الرءوس زوجي. لذا

الرقم اللوني = 2

مثال 3: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

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

مثال 4: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

حل: في الرسم البياني أعلاه، يوجد لونان مختلفان لستة رؤوس، ولم يتم تلوين أي من القمم المجاورة بنفس اللون. في هذا الرسم البياني، عدد الرءوس زوجي. لذا

الرقم اللوني = 2

الرسم البياني المخطط

يُعرف الرسم البياني بأنه رسم بياني مخطط إذا تم رسمه في مستوى. يجب ألا تتقاطع حواف الرسم البياني للمخطط مع بعضها البعض.

رقم لوني:

1. في الرسم البياني المخطط، يجب أن يكون الرقم اللوني أقل من أو يساوي 4.
2. يمكن أيضًا عرض الرسم البياني للمخطط من خلال جميع الرسوم البيانية للدورة المذكورة أعلاه باستثناء المثال 3.

أمثلة على الرسم البياني المسوي:

هناك أمثلة مختلفة للرسوم البيانية المسطحة. يتم وصف بعضها على النحو التالي:

مثال 1: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

حل: في الرسم البياني أعلاه، هناك 3 ألوان مختلفة لثلاثة رؤوس، ولا تتقاطع أي من حواف هذا الرسم البياني مع بعضها البعض. لذا

اسم المستخدم

الرقم اللوني = 3

هنا، الرقم اللوني أقل من 4، لذا فإن هذا الرسم البياني هو رسم بياني مستوي.

مثال 2: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

حل: في الرسم البياني أعلاه، يوجد لونان مختلفان لأربعة رؤوس، ولا تتقاطع أي من حواف هذا الرسم البياني مع بعضها البعض. لذا

الرقم اللوني = 2

هنا، الرقم اللوني أقل من 4، لذا فإن هذا الرسم البياني هو رسم بياني مستوي.

مثال 3: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

حل: في الرسم البياني أعلاه، هناك 5 ألوان مختلفة لخمسة رؤوس، ولا تتقاطع أي من حواف هذا الرسم البياني مع بعضها البعض. لذا

الرقم اللوني = 5

هنا، الرقم اللوني أكبر من 4، لذا فإن هذا الرسم البياني ليس رسمًا بيانيًا مستويًا.

مثال 4: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

حل: في الرسم البياني أعلاه، يوجد لونان مختلفان لستة رؤوس، ولا تتقاطع أي من حواف هذا الرسم البياني مع بعضها البعض. لذا

الرقم اللوني = 2

هنا، الرقم اللوني أقل من 4، لذا فإن هذا الرسم البياني هو رسم بياني مستوي.

الرسم البياني الكامل

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

رقم لوني

في الرسم البياني الكامل، سيكون العدد اللوني مساويًا لعدد القمم في هذا الرسم البياني.

مسج هذه النقرة

أمثلة على الرسم البياني الكامل:

هناك أمثلة مختلفة للرسوم البيانية الكاملة. يتم وصف بعضها على النحو التالي:

مثال 1: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

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

الرقم اللوني = 4

مثال 2: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

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

الرقم اللوني = 5

مثال 3: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

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

الرسم البياني الثنائي

يُعرف الرسم البياني بأنه رسم بياني ثنائي إذا كان يحتوي على مجموعتين من القمم، A وB. يمكن لرأس A أن يتصل فقط برؤوس B. وهذا يعني أن الحواف لا يمكنها ربط القمم بمجموعة.

رقم لوني

في أي رسم بياني ثنائي، يكون الرقم اللوني دائمًا يساوي 2.

أمثلة على الرسم البياني الثنائي:

هناك أمثلة مختلفة للرسوم البيانية ثنائية الأطراف. يتم وصف بعضها على النحو التالي:

مثال 1: في الرسم البياني التالي، علينا تحديد الرقم اللوني.

حل: هناك مجموعتان مختلفتان من القمم في الرسم البياني أعلاه. لذا فإن العدد اللوني لجميع الرسوم البيانية الثنائية سيكون دائمًا 2. لذا

الرقم اللوني = 2

شجرة:

سيُعرف الرسم البياني المتصل بالشجرة إذا لم تكن هناك دوائر في هذا الرسم البياني. في الشجرة، الرقم اللوني يساوي 2 بغض النظر عن عدد القمم الموجودة في الشجرة. كل رسم بياني ثنائي هو أيضًا شجرة.

رقم لوني

في أي شجرة، الرقم اللوني يساوي 2.

تعريف الكمبيوتر

أمثلة على الشجرة:

هناك أمثلة مختلفة للشجرة. يتم وصف بعضها على النحو التالي:

مثال 1: في الشجرة التالية، علينا تحديد الرقم اللوني.

حل: هناك لونان مختلفان لأربعة رؤوس. يجب أن تحتوي الشجرة التي تحتوي على أي عدد من القمم على الرقم اللوني مثل 2 في الشجرة أعلاه. لذا،

الرقم اللوني = 2

مثال 2: في الشجرة التالية، علينا تحديد الرقم اللوني.

حل: هناك لونان مختلفان لخمسة رؤوس. يجب أن تحتوي الشجرة التي تحتوي على أي عدد من القمم على الرقم اللوني مثل 2 في الشجرة أعلاه. لذا،

الرقم اللوني = 2

مثال واقعي للرقم اللوني

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

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