تلوين المخطط بلونين: افحص الدورة لا عدد الرؤوس

الخلاصة السريعة

الدورة A→B→C→D→E→A لا تقبل تلوينًا بلونين يختلف عند طرفي كل حافة: بعد التناوب يصل E إلى لون A نفسه، وبينهما حافة. أما دورة A→B→C→D→A مع E معزولًا فتقبل لونين، رغم أن مجموع رؤوس الرسم خمسة أيضًا.

• المخطط ثنائي التقسيم يقسم الرؤوس إلى مجموعتين منفصلتين، وتصل كل حافة بينهما. هذا يكافئ تلوين الرؤوس بلونين بحيث يختلف طرفا كل حافة. [1]
• في مخططنا البسيط غير الموجه، وجود دورة فردية يمنع اللونين؛ ويقبل المخطط اللونين إذا وفقط إذا لم توجد فيه دورة فردية. افحص جميع المكونات، لا جزءًا واحدًا فقط. [1]
• في الدورة الخماسية، اختيار A أخضر يفرض B ذهبيًا و C أخضر و D ذهبيًا و E أخضر. الحافة E–A هي موضع التعارض؛ تبادل اسمي اللونين لا يزيله.
• في الدورة الرباعية، نلون A و C بالأخضر، و B و D بالذهبي. الحواف A–B و B–C و C–D و D–A كلها بين لونين مختلفين.
• إضافة E معزولًا إلى الدورة الرباعية تجعل المجموع 5 رؤوس، دون إفساد التلوين. وإضافة F معزولًا إلى الدورة الخماسية تجعل المجموع 6، دون إزالة التعارض. طول الدورة هو المهم هنا، لا زوجية مجموع الرؤوس.
• إضافة مثلث منفصل F,G,H إلى الدورة الرباعية تمنع تلوين المخطط كله بلونين. المثلث دورة بطول 3، حتى لو كانت الدورة الرباعية وحدها صالحة. لا يلزم تساوي حجمي المجموعتين.

اللون يحدد المجموعة، والحافة تحدد شرط الاختلاف

المخطط ثنائي التقسيم يسمح بوضع كل رأس في إحدى مجموعتين منفصلتين، دون حافة تصل رأسين في المجموعة نفسها. ويمكن التعبير عن ذلك بلونين مختلفين عند طرفي كل حافة. [1]

نعالج هنا مخططًا غير موجه وبسيطًا، بلا حلقات ذاتية أو حواف متوازية. اللون صفة للرأس، لا للحافة، ونعد الخطوط اتصالات فقط؛ أطوالها وزواياها على الصفحة لا تحدد قيدًا جديدًا.

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

تعني الدورة هنا مسارًا مغلقًا يعود إلى البداية، دون تكرار الرؤوس الداخلية أو الحواف، وطولها عدد حوافها. سنكتب أسماءها بالأسهم لتوضيح ترتيب التتبع، لكن خطوط المخطط نفسه غير موجهة؛ السهم في قائمة الأسماء لا يضيف اتجاهًا إلى الحافة.

دورة من خمس حواف تفرض تعارضًا عند الإغلاق

رسمنا الأول يضم A و B و C و D و E، وحوافه كاملة هي A–B و B–C و C–D و D–E و E–A. لا توجد حواف إضافية. نبدأ بـ A أخضر، ثم نتتبع الدورة بالترتيب A→B→C→D→E→A.

حتى تختلف ألوان طرفي A–B، يجب أن يكون B ذهبيًا. ثم تفرض B–C أن يكون C أخضر، وتفرض C–D أن يكون D ذهبيًا، وتفرض D–E أن يكون E أخضر. عند إغلاق الدورة، نجد الحافة E–A بين رأسين أخضرين، فتخالف الشرط.

الجدول يعرض فحص الحواف الخمس للتلوين المفروض بدءًا من A أخضر. اللون الأحمر للحافة E–A في الصورة يبرز التعارض، ولا يمثل لونًا ثالثًا للرؤوس. نجاح الحواف الأربع الأولى لا يكفي لقبول الرسم كله.

لا يحل المشكلة أن نبدأ A ذهبيًا: ستتبادل جميع الألوان، ويصبح E ذهبيًا أيضًا، وتبقى الحافة E–A بين لونين متساويين. كما لا يمكن تغيير E وحدها إلى الذهبي، لأن ذلك يجعلها مساوية للون D ويخالف D–E. لذلك استبعدنا كلا الاختيارين الممكنين للون البداية.

أربع حواف تغلق التناوب دون تعارض

نغيّر الحواف: نحذف D–E و E–A، ونضيف D–A. نبقي الرؤوس الخمسة، لكن E يصبح معزولًا. الحواف الآن A–B و B–C و C–D و D–A، وهي دورة A→B→C→D→A من أربع حواف.

اختر A و C أخضرين، و B و D ذهبيين. تصل A–B بين الأخضر والذهبي، و B–C بين الذهبي والأخضر، و C–D بين الأخضر والذهبي، و D–A بين الذهبي والأخضر. كل الحواف تحقق الاختلاف، فلا يوجد تعارض عند إغلاق هذه الدورة.

اخترنا E أخضر في الصورة الداخلية، فتكون المجموعتان A,C,E و B,D. ليس لـ E أي حافة، فلا يفرض هذا الرأس المعزول لونًا على أحد. ويمكن في هذا المثال إعطاؤه الذهبي بدل الأخضر دون تغيير صحة الحواف الأربع.

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

عدد الرؤوس كله لا يحدد زوجية الدورة

في الرسم الأول خمسة رؤوس ودورة بطول 5، ولا يصلح التلوين. في الرسم الثاني خمسة رؤوس أيضًا، لكنها موزعة على دورة بطول 4 ورأس معزول، ويصلح التلوين. العدد الكلي نفسه أعطى حكمين مختلفين لأن الحواف اختلفت.

ولعكس الالتباس، ارجع إلى الدورة الخماسية الأصلية وأضف F بلا حواف. صار المجموع 6 رؤوس، لكنه لا يغيّر الحواف الخمس ولا تعارض E–A. لا يؤدي كون العدد الكلي زوجيًا إلى إمكان اللونين.

القاعدة للمخطط غير الموجه هي أن وجود دورة فردية يمنع كونه ثنائي التقسيم؛ وإذا كانت كل دوراته زوجية، أمكن تقسيمه إلى الجانبين. [1]

ليس المطلوب أن تكون هناك دورة أصلًا حتى نقبل الرسم. فثلاثة رؤوس A و B و C في سلسلة A–B و B–C تقبل A و C بالأخضر و B بالذهبي، مع أنها لا تحتوي دورة، وعدد رؤوسها فردي.

راجع الجزء المنفصل أيضًا، ثم افحص كل الحواف

خذ الدورة الرباعية A,B,C,D وحدها، وأضف مثلثًا منفصلًا برؤوس F و G و H وحواف F–G و G–H و H–F. يبدأ التلوين في الرباعية بنجاح، لكن ذلك لا يقول شيئًا عن المثلث المنفصل.

إذا كان F أخضر، أجبرنا F–G على G ذهبي، ثم G–H على H أخضر. تبقى H–F بين رأسين أخضرين. ولو تبادلنا اسمي اللونين لتكرر التعارض نفسه. لا يمكن تلوين المخطط المكوّن من الجزأين بلونين، بسبب الدورة الفردية F→G→H→F.

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

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