غابة خطية لكل زوج ألوان: لماذا ترفض النجمة لونين؟

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

لأن رسم اللونين في النجمة ذات الثلاث أوراق يتفرع عند المركز بدرجة 3، فلا يكون مجموعة مسارات. المركز 1 والأوراق 2 و 2 و 3 ينجح بأقل 3؛ لونان يفرضان اتفاق كل الأوراق، فيعيدان التفرع المرفوض.

• نعني بالتلوين الخطي هنا تلوينًا صحيحًا للرؤوس يكون فيه الرسم المستحث بكل زوج ألوان مجموعة مسارات منفصلة؛ وعدده أقل عدد ألوان يحققه. [1] [4] المسار المنفرد قد يكون رأسًا بلا حواف. نموذجنا محدود وبسيط وغير موجه وغير فارغ الرؤوس؛ نلون الجميع، حتى المعزول، بأسماء ألوان حرة. كل زوج غابة بلا دورة ودرجته لا تتجاوز 2؛ المعزول ملون، والخالي يحتاج 1 لا 0. تبديل أسماء الألوان يحفظ النجاح.
• التلوين الصحيح العادي يفرض اختلاف لون طرفي كل حافة، ويبحث عن أقل عدد ألوان. [2] نحتفظ بالصحة، ونضيف شرط المسارات في كل زوج ألوان؛ لا نلون الحواف. P4 بحواف AB BC CD يقبل 1 2 1 2 بأقل 2. نجمة AB AC AD بالتعيين 1 2 2 2 صحيحة لكنها تفشل عند A ذي الثلاثة جيران بلون 2؛ 1 2 2 3 يصلح بأقل 3، لأن اللونين يفرضان اتفاق الأوراق. الحد اثنان لكل لون آخر على حدة، لا اثنان لكل الجيران، ولا للجيران بلون الرأس نفسه؛ الصحة تجعل عدد الجيران بلون الرأس صفرًا.
• اللادوري يفرض غابة لكل زوج ألوان، والنجمي يفرض نجومًا، أو ثلاثة ألوان على الأقل لكل مسار رباعي. [3] شرطنا يفرض مسارات، فيمنع التفرع والدورة لكنه يسمح بمسار رباعي بلونين. P4 يقبل 2 خطيًا لكنه يحتاج 3 نجميًا؛ النجمة الثلاثية تحتاج 3 خطيًا لكنها تقبل 2 نجميًا. فلا ترتيب ثابت بين الخطي والنجمي؛ الخطي يحقق اللادوري والصحيح دائمًا. يستعمل مرجع آخر اسم التلوين الخطي لشرط وجود رأس بلون وحيد في كل مسار. [5] هذا تعريف مختلف؛ نعتمد هنا غابة خطية لكل زوج ألوان. P4 بالشاهد 1 2 1 2 ينجح عندنا، لكن المسار كله لا يملك لونًا وحيدًا، فيفشل للتعريف الآخر.
• C4 بالتناوب 1 2 1 2 يحقق سقف اثنين عند كل رأس، لكنه يفشل بسبب الدورة بلونين؛ 1 2 1 3 ينجح بأقل 3، واللونان يفرضان التناوب المرفوض. C6 لا تحوي دورة رباعية، لكنها ترفض 1 2 1 2 1 2 لدورة الستة؛ 1 2 1 2 1 3 ينجح بأقل 3، فكل زوج مسارات، رغم أن A B C D بلونين يفشل نجميًا. لا نحذف حواف ولا نحصر منع الدورات في طول 4، ولا نفرض رسمًا مستحثًا للدورة. الغابة ذات الدرجة القصوى 2 تكون مسارات: لا تفرع ولا إغلاق. نجميًا C6 تقبل 1 2 3 1 2 3 بأقل 3: كل نافذة رباعية فيها ثلاثة ألوان، واللونان يفرضان التناوب المرفوض.
• نجمة بخمس أوراق تقبل المركز 1 والأوراق 2 2 3 3 4 بأقل 4: كل لون أوراق يتسع لاثنتين فقط، واللون الخاص بالمركز مختلف عن الجميع. لنجمة ذات m أوراق، حيث m موجب، الأقل 1+ceil(m/2)؛ ceil تعني التقريب إلى أعلى عدد صحيح. تبقى الدرجة الأصلية للمركز 5 في الشاهد، لكن لكل لون آخر جارَان أو أقل. K2,3 تحتاج 4 بالشاهد 1 2 3 3 4، و K3,3 تحتاج 5 بالشاهد 1 2 3 4 4 5. في K_p,q ذي الجانبين الموجبين، كل فئة لا تسع أكثر من رأسين، وأحد الجانبين لا بد أن تكون ألوانه مختلفة كلها لمنع دورة رباعية؛ الأقل min(p+ceil(q/2),q+ceil(p/2))، بتفريد جانب وتجميع الآخر أزواجًا.
• P5 و P6 يقبلان التناوب بأقل 2، والحافتان المنفصلتان وحافة مع معزولين تحتاجان 2، والخالي 1. C5 تقبل 1 2 1 2 3 بأقل 3؛ المثلث 1 2 3 والماسة 2 3 1 1 يحتاجان 3، و K4 بأربعة ألوان مختلفة يحتاج 4. نجميًا تحتاج P4 و P5 و P6 إلى 3، و C5 إلى 4؛ أما النجمتان فتكفيهما 2، و K2,3 و K3,3 تحتاجان 3 و 4، أقل من 4 و 5 خطيًا. الشواهد والبراهين تحدد الأقل: نعرض نجاحًا ونستبعد كل عدد أصغر، ونفحص كل حافة وكل زوج ألوان.
• حصر 64 رسمًا رباعيًا أعطى 960 تقسيمًا بعد تجاهل إعادة أسماء الألوان: 337 صحيحًا، و 330 خطيًا، و 334 لادوريًا، و 322 نجميًا. بحث الأقل جرب 1133 تعيينًا كاملًا؛ التوزيع 1 في رسم، و 2 في 33، و 3 في 29، و 4 في رسم. زاد الخطي عن العادي في 7: ثلاث C4 مسماة وأربع نجوم بثلاث أوراق، وزاد عن اللادوري في النجوم الأربع. قل عن النجمي في 12 مسارًا P4 وزاد عنه في النجوم الأربع. عد C4 هو 24/8=3، و P4 هو 24/2=12، والنجوم الأربع باختيار المركز. على أربعة رؤوس لا يتفرع زوج ألوان إلا بهذه النجمة، ولا تقع دورة ثنائية إلا C4. فحص آخر للمكونات راجع درجة 2 وعدد حواف كل مكون يساوي عدد رؤوسه ناقص 1، واتفق في 16 مثالًا و 64 رسمًا والقوائم الكاملة للأقل؛ راجع رأسًا واحدًا ورأسين، ومولد التقسيمات مشترك. الأعداد ليست أزمنة تنفيذ، ولا نعمم حد 3؛ K3,3 خارج الحصر تحتاج 5.

مسارات في كل زوج ألوان: شرط الدرجة وشرط الدورة

نعني بالتلوين الخطي هنا تلوينًا صحيحًا للرؤوس يكون فيه الرسم المستحث بكل زوج ألوان مجموعة مسارات منفصلة؛ وعدده أقل عدد ألوان يحققه. [1] [4] المسار المنفرد قد يكون رأسًا بلا حواف.

التلوين الصحيح العادي يفرض اختلاف لون طرفي كل حافة، ويبحث عن أقل عدد ألوان. [2] نحتفظ بالصحة، ونضيف شرط المسارات في كل زوج ألوان؛ لا نلون الحواف.

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

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

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

الرؤوس كلها ملونة في نموذج بسيط وغير موجه، والألوان أسماء حرة قابلة للتبديل. نبحث عن أقل عدد مستعمل، لا أكبر رقم لون. المعزول ينجح لكنه يبقى ملونًا؛ الرسم بلا حواف يحتاج 1 لا 0 ما دامت رؤوسه غير فارغة.

النجمة ذات الثلاث أوراق تحتاج الثالث، و P4 يقبل لونين

ثبت نجمة مركزها A وأوراقها B C D، والحواف AB AC AD فقط. المركز 1 والأوراق 2 يعطي تلوينًا صحيحًا، لكنه يجعل A ذا ثلاثة جيران بلون 2. رسم اللونين نجمة متفرعة بدرجة 3، فلا يكون مجموعة مسارات.

اختر A1 B2 C2 D3. زوج 1 و 2 يعطي المسار B A C، ولا يدخل D في هذا الزوج لأن لونه 3؛ وزوج 1 و 3 يعطي حافة AD، وزوج 2 و 3 بلا حواف. ينجح الشاهد بثلاثة.

في أي تلوين صحيح بلونين لهذه النجمة، لا تحمل ورقة لون المركز، فتأخذ الأوراق الثلاث اللون الآخر نفسه، ويظهر التفرع. اللون الواحد مستحيل بالحواف، فيثبت الأقل 3؛ إخفاق شاهد اللونين هنا يعم الجميع بسبب الصحة.

خذ بدلًا منها P4 على A B C D بحواف AB BC CD. الشاهد 1 2 1 2 صحيح، ورسم اللونين مسار واحد درجتاه الداخليتان 2 وطرفاه 1، ولا دورة. ينجح بأقل 2 لأن الحافة تمنع 1.

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

السقف عند اثنين لا يمنع دورة اللونين وحده

في C4 بحواف AB AD BC CD، الشاهد 1 2 1 2 صحيح، وكل رأس يملك جارَين من اللون الآخر. يحقق سقف العدد 2، لكن رسم اللونين دورة لا مسار؛ فيفشل خطيًا.

الشاهد 1 2 1 3 صحيح. زوج 1 و 2 يعطي المسار A B C، وزوج 1 و 3 يعطي A D C، وزوج 2 و 3 بلا حواف. كل زوج غابة خطية، فينجح بثلاثة. كل تلوين صحيح بلونين في C4 يفرض التناوب المرفوض، فيثبت الأقل 3.

C6 بحواف AB BC CD DE EF FA ترفض 1 2 1 2 1 2 لدورة الستة بلونين، رغم أن كل درجة في رسم الزوج 2، ورغم غياب دورة رباعية في الرسم. لا نحصر شرط اللادورية في أربع حواف.

اختر 1 2 1 2 1 3. زوج 1 و 2 يعطي المسار A B C D E؛ وزوج 1 و 3 يعطي المسار A F E ومعزولًا C؛ وزوج 2 و 3 بلا حواف. الصحة محفوظة، فينجح خطيًا بأقل 3 لأن أي حل صحيح بلونين يفرض التناوب حول الدورة كلها.

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

الخطي والنجمي لا يترتبان، والاسم قد يعني شرطًا آخر

اللادوري يفرض غابة لكل زوج ألوان، والنجمي يفرض نجومًا، أو ثلاثة ألوان على الأقل لكل مسار رباعي. [3] شرطنا يفرض مسارات، فيمنع التفرع والدورة لكنه يسمح بمسار رباعي بلونين.

يستعمل مرجع آخر اسم التلوين الخطي لشرط وجود رأس بلون وحيد في كل مسار. [5] هذا تعريف مختلف؛ نعتمد هنا غابة خطية لكل زوج ألوان.

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

النجمة ذات الثلاث أوراق بالمركز 1 والأوراق 2 تنجح نجميًا، لأن أطول مسار فيها ثلاثة رؤوس فقط؛ الأقل 2 نجميًا بحكم وجود حافة. لكنها تفشل خطيًا لتفرع اللونين بدرجة 3. لذلك لا نقول إن أحد الشرطين يتضمن الآخر عمومًا.

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

في تعريف اللون الوحيد لكل مسار، الشاهد 1 2 1 2 على P4 يفشل: يظهر اللون 1 مرتين واللون 2 مرتين، فلا يوجد رأس بلون يظهر مرة واحدة في المسار كله. نجاحه في سؤالنا لا يجعله حلًا لذلك التعريف؛ لهذا نصرح بغابة خطية لكل زوج ألوان.

أزواج الأوراق تصلح نجمة درجتها خمسة

في نجمة مركزها A وخمس أوراق B C D E F، اختر A1 B2 C2 D3 E3 F4. زوج 1 و 2 يعطي B A C، وزوج 1 و 3 يعطي D A E، وزوج 1 و 4 يعطي حافة AF؛ أزواج ألوان الأوراق بلا حواف. ينجح بأربعة رغم أن درجة A الأصلية 5.

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

لنجمة ذات m أوراق، حيث m موجب، الأقل 1+ceil(m/2). نعني بـ ceil التقريب إلى أعلى عدد صحيح: لا يتسع كل لون أوراق إلا لاثنتين، فتحتاج ceil(m/2) ألوان، ثم لون المركز. إعطاء كل زوج أوراق لونًا، وللورقة المنفردة لونًا عند الحاجة يحقق الحد؛ في كل زوج ألوان تكون النتيجة مسارًا أو حافة أو معزولات.

في K_p,q، حيث p و q حجما الجانبين وموجبان، كل رأس في أحدهما متصل بكل رأس في الآخر. الصحة تجعل ألوان الجانبين منفصلة. كل فئة لون داخل جانب لا تتسع لأكثر من رأسين، لأن أي رأس من الجانب الآخر يرى الفئة كلها من لون واحد.

إذا احتوى كل جانب فئة لون من رأسين أو أكثر، ظهرت دورة رباعية بلونين. لذلك لا بد أن تكون كل ألوان أحد الجانبين مختلفة. إذا فردنا جانب p، نحتاج p ألوان له وceil(q/2) للآخر؛ وإذا فردنا q، نحتاج q+ceil(p/2).

الأقل إذن min(p+ceil(q/2),q+ceil(p/2)). الصغرى هي أصغر الخيارين؛ البناء بتفريد أحد الجانبين وتجميع الآخر أزواجًا يحقق كل خيار، وحد الدرجة ومنع الدورة يفرضان واحدًا منهما على كل حل. K2,3 يقبل 1 2 3 3 4 بأقل 4، و K3,3 يقبل 1 2 3 4 4 5 بأقل 5؛ لا نستنتج حدًا عامًا 3 من الرسوم الرباعية.

دورات ومسارات وماسة: الشواهد والأعداد للمقارنة

P5 يقبل 1 2 1 2 1، و P6 يقبل 1 2 1 2 1 2 خطيًا بأقل 2؛ رسم اللونين كله مسار، والحواف تمنع 1. نجميًا يحتاجان 3 لأنهما يحتويان P4؛ الشاهدان 1 2 1 3 1 و 1 2 1 3 1 2 ينجحان، إذ تحوي كل نافذة رباعية ثلاثة ألوان.

C5 تقبل 1 2 1 2 3 خطيًا بأقل 3. صحتها محفوظة، وكل رسم زوج ألوان مسارات: الدورة الأصلية درجتها 2، ولا يمكن أن تقع دورة بلونين إلا إذا أخذنا الدورة كلها، وفي الشاهد ثلاثة ألوان. اللونان يفشلان للصحة في الدورة الفردية.

نجميًا تحتاج C5 إلى 4: أي تلوين صحيح بثلاثة يستعمل فئات بحجوم 2 و 2 و 1، لأن أكبر مجموعة مستقلة فيها حجمها 2. حذف الرأس الوحيد في لونه يترك P4 بلونين، فيفشل نجميًا. الشاهد 1 2 1 3 4 صحيح ونجمي لأنه لا يتكرر فيه سوى لون واحد، والمسار الرباعي الصحيح بلونين يكرر كليهما.

المثلث يقبل 1 2 3 بأقل 3، و K4 يقبل أربعة ألوان مختلفة بأقل 4؛ الصحة نفسها تفرض هذين الحدين، وكل زوج ألوان فيهما حافة أو رؤوس بلا حواف. الماسة AB AC AD BC BD تقبل 2 3 1 1 بأقل 3: زوج 1 و 2 يعطي C A D، وزوج 1 و 3 يعطي C B D، وزوج 2 و 3 حافة AB؛ والمثلث ABC يفرض 3. كل هذه المكونات نجمة أو رأس منفرد، فينجح النجمي أيضًا بالحد نفسه؛ والمسارات كلها غابات، فتنجح اللادورية أيضًا.

نجميًا ولادوريًا، النجمتان بثلاث وخمس أوراق تقبلان المركز 1 وكل الأوراق 2 بأقل 2؛ النجمي لا يجد مسارًا رباعيًا، واللادوري لا يجد دورة. أما K2,3 و K3,3 فالأقل 3 و 4 لهما في هذين السؤالين: أعط رؤوس الجانب الأصغر ألوانًا مختلفة، والآخر لونًا واحدًا. كل زوج نجمة؛ وتكرار لون على كل جانب يولد دورة رباعية، فيفرض أن يكون أحد الجانبين بلا لون مكرر، فيثبت min(p,q)+1. الخطي يضيف سقف 2، فيزيد العدد إلى 4 و 5.

الحافتان المنفصلتان AB و CD تقبلان 1 2 1 2، وحافة AB مع معزولين C و D تقبل 1 2 1 1، بأقل 2 في التلوين العادي واللادوري والخطي والنجمي. الخالي من الحواف يقبل 1 للجميع بأقل 1؛ المعزول ملون أيضًا.

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

سبعة رسوم رباعية يزيد فيها العدد عن العادي

ثبتنا A B C D والحواف المحتملة AB AC AD BC BD CD. إبقاء أو حذف كل منها يعطي 2^6=64 رسمًا مسمى. جربنا 15 تقسيمًا للرؤوس في كل رسم بعد تجاهل إعادة أسماء الألوان، فالمجموع 960.

نجح 337 تقسيمًا للصحة، و 330 للخطي، و 334 للادوري، و 322 للنجمي. بحث للأقل بزيادة عدد الألوان جرب 1133 تعيينًا كاملًا حتى أول نجاح في كل رسم؛ توزيع الأقل الخطي 1 في رسم، و 2 في 33، و 3 في 29، و 4 في رسم واحد. هذه ليست أزمنة تنفيذ.

زاد الخطي عن العادي في 7 رسوم: ثلاث C4 مسماة وأربع نجوم بثلاث أوراق؛ وزاد عن اللادوري في النجوم الأربع فقط. قل عن النجمي في 12 رسمًا من P4، وزاد عنه في النجوم الأربع. النجوم تعد باختيار مركز من الرؤوس الأربعة، و C4 بعد 24 ترتيبًا تقسم على أربع بدايات واتجاهين: 24/8=3، و P4 يقسم على اتجاهين: 24/2=12.

على أربعة رؤوس، التفرع في رسم زوج ألوان يحتاج رأسًا وثلاثة جيران بلون واحد؛ الصحة تمنع حافة بين الجيران، فيكون الرسم النجمة الثلاثية نفسها. والدورة الثنائية الصحيحة لا بد أن تكون C4؛ لا قطر لها في رسم ثنائي. هذان سببَا الزيادة عن العادي.

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

فحص آخر بنى المكونات المتصلة لكل زوج ألوان، وراجع ألا تزيد الدرجة الداخلية على 2، وأن عدد حواف كل مكون يساوي عدد رؤوسه ناقص 1. تحت الاتصال، هذا يتحقق للغابة ويكشف الدورة؛ ومع الدرجة 2 تكون المكونات مسارات. اتفقت القوائم الكاملة للأقل وأعداد التعيينات والشاهد الأول في 16 مثالًا و 64 رسمًا مع فحص الدورات الصريحة وعد الجيران من كل لون.

راجعنا رأسًا واحدًا ورسمين على رأسين بحافة وبدونها؛ مولد التقسيمات مشترك، فلا ندعي مراجعًا مستقلًا بالكامل أو مراجعة بشرية. C5 و C6 و K2,3 و K3,3 والمثلث ونجمة الخمس والمسارات الأطول خارج الحصر الرباعي؛ K3,3 تحتاج 5، فلا حد عام 3 مستنتج من الأربعة.

الأمثلة والعد والبراهين من إعداد المقال؛ ثبت معنى التلوين والرؤوس والحواف، ثم افحص كل زوج ألوان وقدم شاهدًا وحدًا أدنى قبل تسمية العدد الأقل.