تلوين المخطط
لوّن مخططًا بأقل عدد ممكن من الألوان
حول هذه الآلة الحاسبة
تجد حاسبة تلوين المخطط العدد الصبغي χ(G) — أقل عدد من الألوان اللازمة لتلوين رؤوس مخطط بحيث لا يصل أي ضلع بين رأسين لهما اللون نفسه — وتعرض تلوينًا أمثل واحدًا. أدخل عدد الرؤوس وقائمة الأضلاع؛ تحسب χ بدقة عبر بحث التفريع والتقييد، وتُبلغ عن الدرجة العظمى Δ وأكبر زمرة ω (حد أدنى على χ)، وتُميّز المخططات ثنائية التجزئة والكاملة، وترسم المخطط الملوَّن. مفيدة للجدولة وتخصيص السجلّات وتلوين الخرائط ودراسة الأعداد الصبغية.
كيفية تلوين مخطط
- أدخل عدد الرؤوس؛ تُرقَّم من 1 إلى n.
- اسرد الأضلاع كأزواج مثل 1-2, 2-3 — زوج واحد لكل وصلة.
- اقرأ العدد الصبغي χ(G) واللون المُخصَّص لكل رأس.
- قارن χ بأكبر زمرة ω لترى سبب الحاجة إلى هذا العدد من الألوان، أو حمّل مثالًا جاهزًا للاستكشاف.
أمثلة شائعة
- المثلث (K₃) يحتاج 3 ألوان — كل زوج من رؤوسه متجاور.
- الدورات الزوجية ثنائية التجزئة وتحتاج لونين فقط؛ الدورات الفردية مثل C₅ تحتاج 3.
- المخطط الكامل Kₙ يحتاج n ألوان بالضبط.
- أكبر زمرة بحجم ω تفرض ω ألوان على الأقل، فيكون χ(G) ≥ ω.
- مخطط غروتش يحتاج 4 ألوان لكنه لا يحتوي أي مثلث، فقد يتجاوز χ عدد الزمرة.
الأسئلة الشائعة
ما هو العدد الصبغي؟
العدد الصبغي χ(G) هو أصغر عدد من الألوان اللازم لتلوين رؤوس مخطط بحيث لا يربط أي ضلع رأسين لهما اللون نفسه.
كيف يُوجَد أقل عدد من الألوان؟
لأن المخطط صغير، تبحث الحاسبة بدقة: تجرّب لونًا واحدًا، ثم لونين، وهكذا، وتُرجع أول عدد يوجد له تلوين سليم. هذا العدد مضمون أنه الحد الأدنى الحقيقي.
ما الدرجة العظمى وأكبر زمرة؟
الدرجة العظمى Δ هي أكبر عدد من الأضلاع يلتقي عند رأس واحد. أكبر زمرة ω هي أكبر مجموعة من الرؤوس المتجاورة جميعًا؛ ولأنها يجب أن تختلف كلها، فإن χ(G) لا يقل عن ω.
لماذا قد يحتاج مخطط خالٍ من المثلثات إلى ألوان كثيرة؟
الزمرة الكبيرة تفرض ألوانًا كثيرة، لكنها ليست السبب الوحيد. الدورات الفردية ومخططات مثل مخطط غروتش تحتاج ألوانًا إضافية حتى دون أي مثلث، فقد يكون χ(G) أكبر من عدد الزمرة.
هل هناك حد لحجم المخطط؟
نعم. تلوين المخطط الدقيق صعب حسابيًا، لذا تحدّ الحاسبة المخطط بـ 12 رأسًا لإبقاء النتائج فورية ودقيقة.