تلوين الحواف النجمي: لماذا يرفض مسارًا بلونين دون دورة؟

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

لأن التلوين النجمي يمنع المسار المفتوح ذي أربع حواف من الاقتصار على لونين، حتى دون دورة. في A-B-C-D-E، التلوين الصحيح بلونين يفرض التناوب 1 2 1 2، فيفشل الشرط النجمي. تغيير DE إلى لون ثالث يعطي 1 2 1 3، فيبقى صحيحًا ويجعل المسار يستعمل ثلاثة ألوان.

• تلوين الحواف النجمي تلوين صحيح يمنع مسارًا أو دورة بطول أربع حواف من استعمال لونين فقط؛ ومؤشره اللوني هو أقل عدد من الألوان يحقق الشرط. [1] نفترض رسمًا محدودًا وبسيطًا وغير موجه، بلا حلقات أو أوزان، وبقائمة رؤوس غير فارغة. نلون كل حافة مرة؛ طول المسار يحصي الحواف، لا الرؤوس.
• التلوين الصحيح للحواف يفرض اختلاف اللون بين الحافتين المتلاقيتين عند رأس، ويبحث عن أقل عدد من الألوان. [2] المسار المحظور المفتوح يملك أربع حواف وخمسة رؤوس مختلفة. المسار AB BC CD ذو ثلاث حواف يقبل 1 2 1 نجميًا، بخلاف التلوين القوي الذي يرفض فئة AB CD بسبب BC بين أطرافها.
• في المسار AB BC CD DE، الأقل العادي 2 واللادوري 2 والنجمي 3. أي تلوين بلونين يفرض التناوب المحظور، والتعيين 1 2 1 3 يحقق 3. وجود ثلاثة ألوان في مكان آخر من الرسم لا يصلح مسارًا ما زال بلونين.
• تحت شرط التلوين الصحيح، يكافئ النجمي أن يكون لكل مكون في اتحاد أي فئتي لون ثلاث حواف على الأكثر. الفئات وحدها مطابقات؛ الاتحاد قد يكون مسارًا بثلاث حواف. لا نحتفظ بحواف الألوان الأخرى بحجة أن أطرافها ضمن الرؤوس.
• في C6، جعل EF باللون 3 في التناوب العادي يمنع الدورة الثنائية، لكنه يبقي AB BC CD DE بالتناوب 1 2 1 2، فيفشل النجمي. التلوين بفئات AB DE، وAF CD، وBC EF يحقق النجمي 3. وفي C4 يكفي تغيير حافة إلى لون ثالث، فيكون العادي 2 والنجمي 3.
• كل نجمي لادوري: الدورة الثنائية ذات أربع حواف ممنوعة، والأطول تحتوي مسارًا مفتوحًا بأربع حواف؛ التلوين الصحيح يمنع دورة فردية بلونين. المثلث والنجمة AB AC AD يحتاجان 3 في العادي والنجمي، والمعزول لا يغير التعيينات، والرسم بلا حواف يحتاج 0 ألوان وتعيينًا فارغًا واحدًا.
• راجعنا 64 رسمًا ناتجًا من حذف حواف محددة من AB AC BC CD CE DE على خمسة أسماء؛ ليست كل الرسوم الخماسية. عبرها 877 تقسيمًا،160 عادية و 144 نجمية، و 87 تقسيمًا أدنى عاديًا و 104 أدنى نجميًا، واختلف الأقلان في 9 مدخلات. اتفق اختبار التشكيلات والمكونات 877 مرة، وراجعنا الأقلين بتعيينات مسماة مستقلة؛ أعداد محدودة لا صيغة عامة أو ادعاء سرعة.

أربع حواف في المسار تعني خمسة رؤوس مختلفة

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

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

الشرط يبدأ بتلوين صحيح، ثم يفحص كل مسار مفتوح من أربع حواف وكل دورة رباعية. في المسار A-B-C-D-E، الرؤوس الخمسة مختلفة والحواف الأربع AB BC CD DE. وفي الدورة A-B-C-D-A، الحواف الأربع تغلق الطريق على أربعة رؤوس.

لا نقصد مسارًا على أربعة رؤوس عند الحديث عن أربع حواف. المسار A-B-C-D له ثلاث حواف فقط، فلا يكون وحده التشكيل الذي يحظره التعريف. هذه نقطة مهمة عند نقل الشرط من أسماء الرؤوس إلى قائمة الحواف.

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

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

المسار المفتوح يضيف قيدًا لا تراه اللا دورية

التلوين الصحيح للحواف يفرض اختلاف اللون بين الحافتين المتلاقيتين عند رأس، ويبحث عن أقل عدد من الألوان. [2]

خذ AB BC CD DE على A B C D E. إذا لونت AB باللون 1، فإن BC تحتاج لونًا مختلفًا عند B. ومع لونين فقط تكون BC باللون 2، ثم CD باللون 1 عند C، ثم DE باللون 2 عند D.

إذن أي تلوين صحيح بلونين يفرض التناوب 1 2 1 2، بعد احتمال تبديل الأسماء. الحواف الأربع مسار مفتوح يستعمل لونين فقط، فيفشل التلوين النجمي. ليس العائق دورة مخفية؛ الأصل نفسه مسار بلا دورات.

أبقِ AB باللون 1 وBC باللون 2 وCD باللون 1، وغير DE إلى اللون 3. عند D نجد 1 و 3 بدل 1 و 2، فلا يتكرر لون عند رأس. التشكيل الوحيد من أربع حواف يستعمل 1 و 2 و 3، فيكون التلوين نجميًا.

ثبت الأقل النجمي 3 لأن أي لونين يفشلان والشاهد الثلاثي ينجح. والأقل العادي 2 لأن التناوب صالح والتقاء حافتين يمنع 1. والأقل اللادوري 2 أيضًا، لأن الرسم بلا دورات؛ شرط اللا دورية لا يمنع المسار المفتوح المتناوب.

الصورة الرئيسية تعرض المسار كاملًا في اللوحتين. اليسار عادي ولادوري لكنه غير نجمي، واليمين نجمي بعد تغيير لون DE فقط. لم نحذف حافة لتقصير المسار، ولم نغلق طرفيه بدائرة جديدة.

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

اتحاد اللونين يسمح بمسار قصير، لا بمكون طويل

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

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

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

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

ليس المطلوب أن يكون اتحاد اللونين مطابقة أو أن يملك الرسم كله ثلاث حواف فقط. في المسار النجمي 1 2 1 3، اتحاد 1 و 2 هو AB BC CD، وهو مسار بثلاث حواف مسموح. اتحاد 1 و 3 هو AB CD DE، وفيه مكونان قصيران.

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

ثلاثة ألوان لادورية قد تفشل نجميًا في السداسية

الدورة A-B-C-D-E-F-A لها AB AF BC CD DE EF. أعطِ AB وCD اللون 1، وAF وBC وDE اللون 2، وEF اللون 3. عند كل رأس لونان مختلفان، والدورة الوحيدة تستعمل ثلاثة ألوان، فيكون التلوين لادوريًا.

لكنه غير نجمي: المسار A-B-C-D-E يأخذ AB باللون 1 وBC باللون 2 وCD باللون 1 وDE باللون 2. لا يغير اللون 3 على EF وجود هذا المسار المتناوب، حتى مع أن المسار جزء من دورة أصلية تستعمل ثلاثة ألوان إجمالًا.

لشاهد نجمي بثلاثة، أعطِ AB وDE اللون 1، وAF وCD اللون 2، وBC وEF اللون 3. حول الدورة، من A إلى B ثم C ثم D ثم E ثم F ثم A، نقرأ 1 و 3 و 2 و 1 و 3 و 2؛ كل أربع حواف متتالية تستعمل الألوان الثلاثة.

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

لونان لا يكفيان نجميًا، لأن التلوين الصحيح بهما يفرض التناوب حول الدورة، فيترك أي أربع حواف متتالية بلونين. ومع شاهد الثلاثة ثبت الأقل 3؛ لكنه لا يعني أن كل تلوين لادوري من ثلاثة في هذه الدورة نجمي.

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

الدورة الرباعية تحتاج الفحص المغلق أيضًا

الدورة C4 لها AB AD BC CD. التلوين العادي بالفئتين AB CD وAD BC صحيح بلونين، لكنه دورة رباعية ثنائية اللون، فيفشل النجمي. لا نحتاج إلى خمسة رؤوس لاكتشاف الفشل هنا لأن شرط الدورة مختلف عن المسار المفتوح.

غير CD وحدها إلى اللون 3، وأبقِ AB باللون 1 وAD وBC باللون 2. عند كل رأس لونان مختلفان، والدورة الرباعية تستعمل ثلاثة ألوان. لا يوجد مسار بسيط بأربع حواف على هذه الرؤوس الأربعة، لأنه كان يحتاج خمسة أسماء مختلفة.

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

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

كل تلوين نجمي لادوري: دورة بلونين في تلوين صحيح تكون زوجية؛ طول 4 ممنوع مباشرة، والطول الأكبر يضم مسارًا من أربع حواف بلونين. والعكس ليس لازمًا، كما أثبت المسار ذو خمسة رؤوس والتعيين الأيسر للسداسية.

المسار الأقصر والنجمة يضبطان معنى الشرط

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

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

في النجمة AB AC AD، الحواف الثلاث تتلاقى كلها عند A، فتحتاج 3 ألوان عادية وتتحقق بثلاثة مختلفة. لا يوجد تشكيل من أربع حواف، فيكون الشاهد نجميًا أيضًا ويثبت الأقل 3؛ اسم الشرط لا يخفض قيد الالتقاء.

وفي المثلث AB AC BC، كل زوج من الحواف متلاقٍ، فيحتاج 3 وتحققها ألوان مختلفة. عدد الحواف 3 لا يتيح مسارًا أو دورة من أربع، فيكون الأقل النجمي 3 أيضًا.

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

الحصر يراجع ست حواف محددة، لا كل الرسوم الخماسية

ثبتنا الأسماء A B C D E والحواف المحتملة AB AC BC CD CE DE فقط. أخذنا كل واحدة من 2^6=64 قائمة ناتجة من إبقاء هذه الحواف أو حذفها، مع إبقاء الرؤوس الخمسة حتى لو انعزل بعضها.

هذا الحصر ليس كل الرسوم البسيطة على خمسة أسماء؛ تلك تسمح بعشرة أزواج محتملة وتعطي 2^10=1024 قائمة. نحن لم نختبر إضافة AD أوAE أوBD أوBE ضمن المجموعة المحددة، فلا نسند إليها أعداد الحصر المحدود.

لكل مدخل حصرنا تقسيمات حوافه إلى فئات غير فارغة، مع توحيد أسماء الألوان حسب أول ظهور. إعادة تسمية 1 و 2 لا تصنع تقسيمًا آخر للفئات نفسها. بلغ مجموع المرشحات 877، والتلوينات العادية 160، والنجمية 144 عبر المدخلات.

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

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

بلغ مجموع التقسيمات التي تحقق الأقل العادي 87، والتي تحقق الأقل النجمي 104، وظهر فرق العددين الأقلين في 9 مدخلات. هذه أعداد حلول مجمعة، لا 87 لونًا أو 104 ألوان في رسم واحد.

راجعنا الأقل بتعيينات ألوان مسماة مستقلة، وتجربة الأعداد تصاعديًا حتى يظهر تلوين صالح. بلغ المرشحون 10400 للعادي و 30445 للنجمي، واتفق الأقل في 64 مدخلًا. تلك تعيينات بأسماء وتجارب مختلفة، فلا نساويها بمرشحات التقسيم 877.

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