الرسم المثالي: هل تكفي مساواة اللون والزمرة؟

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

لا؛ المساواة في الأصل وحده شرط أضعف. في مثالنا χ=ω=3 للأصل، لكن المستحث على D E F G H له χ=3 وω=2، فيرفض المثالية. يكفي مستحث واحد يخالف المساواة لإثبات الفشل، بينما النجاح يحتاج تغطية جميع المستحثات أو حجة تشملها.

• الرسم المثالي يحقق مساواة العدد اللوني وحجم أكبر زمرة في كل رسم جزئي مستحث منه. مساواة القيمتين في الأصل وحده تسمى مثالية ضعيفة، ولا تكفي لتعريف المثالية. [1]
• المستحث بالرؤوس يحتفظ بالأسماء المختارة وبكل حافة أصلية طرفاها ضمنها. [2] لا نحذف حافة بين اسمين باقيين. اختيار خمس حواف فقط من الكامل الخماسي يصنع دورة غير مستحثة؛ حذف الحواف الخمس الأخرى لا يختبر شرط مثالية الأصل.
• نعمل بتلوين رؤوس صحيح: طرفا كل حافة بلونين مختلفين. نرمز لأقل عدد ألوان بـχ، ولحجم أكبر مجموعة رؤوس متجاورة زوجيًا بـω؛ كل زمرة تجبر رؤوسها على ألوان مختلفة، لذا χ≥ω.
• الأصل مثلث ABC ودورة DEFGHD، نوصلهما بالحافة CD؛ ثمانية رؤوس وتسع حواف. المثلث يفرض ثلاثة ألوان، وتلوين صريح بثلاثة يكفي، وأكبر زمرة ABC؛ لذلك χ=ω=3.
• المستحث DEFGH هو دورة خماسية بلا وتر. لا يقبل لونين بسبب العودة بعد عدد فردي من الخطوات، لكنه يقبل ثلاثة؛ لا مثلث فيه، فـχ=3 وω=2. التلوين الجيد للأصل لا يصلح دليلًا على مثاليته.
• التحكم مثلث ABC مع دورة DEFGD والحافة CD، سبعة رؤوس وثماني حواف. إذا بقي المثلث فالقيمتان3؛ وإذا لم يبق صار المستحث قابلًا للونين، فتساويان2 مع وجود حافة، أو1 بلا حواف، أو0 عند غياب الرؤوس.
• من256 مجموعة رؤوس للأصل خالفت سبع المساواة، والتحكم نجح في128 كلها. قارنّا التلوين بطريقتين مستقلتين في32768 حالة عبر1024 رسمًا خماسيًا، مع1100 مدخل مميز محفوظ مؤقتًا. ضمن الخمسة فقط،1012 نجحت في الشرطين؛ مثالنا الثماني يفصل بينهما، ولا ندعي فحص جميع الأحجام.

الشرط يخص كل مستحث، لا الأصل وحده

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

المستحث بالرؤوس يحتفظ بالأسماء المختارة وبكل حافة أصلية طرفاها ضمنها. [2] لا نحذف حافة بين اسمين باقيين. اختيار خمس حواف فقط من الكامل الخماسي يصنع دورة غير مستحثة؛ حذف الحواف الخمس الأخرى لا يختبر شرط مثالية الأصل.

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

العدد اللوني χ هو أقل عدد من الفئات الذي يحقق هذا الشرط. الزمرة مجموعة أسماء، كل زوج مختلف منها متجاور؛ ω حجم أكبر زمرة، لا عدد الزمر ولا عدد الجيران لرأس. زمرة من ثلاثة أسماء تجبر ثلاثة ألوان على الأقل.

لذلك χ≥ω دائمًا في نطاقنا: داخل أي زمرة يجب أن تختلف ألوان جميع رؤوسها. لكن الحد الأدنى الذي تفرضه أكبر زمرة قد لا يكفي للرسم كله. نحتاج بناء تلوين لتحقيق المساواة، ثم لا يزال شرط المثالية يطلبها في كل مستحث.

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

مثلث موصول بدورة خماسية

نثبت الأسماء A B C D E F G H. حواف المثلث AB AC BC، وحواف الدورة DE EF FG GH DH، والحافة الواصلة CD. لا توجد حافة أخرى؛ عددها3+5+1=9، والأصل متصل لأن CD تصل الجزأين.

أكبر زمرة هي ABC ذات الحجم3. داخل الدورة الخماسية لا مثلث، وCD لا تكمل مثلثًا مع رأس ثالث: لا جار مشتركًا لـC وD. كل زمرة عابرة بين الجزأين لا تتجاوز طرفي هذه الحافة، لذلك لا توجد زمرة من أربعة أسماء.

نختار ثلاثة ألوان نرمز إليها1 و2 و3. أعط C وE وG اللون1، وأعط A وD وF اللون2، وأعط B وH اللون3. في المثلث تختلف الألوان الثلاثة؛ وحواف الدورة تصل2 إلى1 ثم2 ثم1 ثم3 ثم2، وحافة CD تصل1 إلى2.

هذا تلوين صحيح بثلاثة ألوان، فيثبت χ≤3. والمثلث يثبت χ≥3؛ إذن χ=3. ومع ω=3 نحصل على المساواة المطلوبة للأصل، لا على حكم يشمل مجموعات الرؤوس الأصغر.

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

المستحث الخماسي يكسر المساواة

اختر S={D,E,F,G,H}. نخرج A وB وC وحوافها، ومنها CD لأن أحد طرفيها خارج S. تبقى DE EF FG GH DH كلها، فهي حواف بين أسماء مختارة. الناتج خمسة رؤوس وخمس حواف، لا الدورة مع مثلث أو مع رأس C.

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

لو حاولنا استعمال لونين، أعط D أحدهما. يجبر DE الرأس E على الثاني، وEF يجعل F على الأول، ثم G على الثاني وH على الأول. الحافة HD ستجمع رأسين باللون الأول؛ تناقض، فلا يكفي لونان.

ثلاثة ألوان تكفي: D وF باللون2، وE وG باللون1، وH باللون3، كما في الأصل. لذلك χ=3 في المستحث. لا مثلث هنا، وكل حافة زمرة من حجم2؛ لهذا ω=2.

حصلنا على χ≠ω في مستحث واحد، فيرفض الأصل شرط المثالية رغم χ=ω=3 له. لا يلزم عرض جميع حالات الفشل لنفي كلمة «كل». اللون الثالث ليس خطأ في تلوين الصورة؛ إنه حاجة لا تستطيع أكبر زمرة ذات الرأسين وحدها التعبير عنها.

تحكم رباعي ينجح في جميع الحالات

نثبت أصلًا آخر على A B C D E F G: المثلث AB AC BC، والدورة DE EF FG DG، والواصلة CD. عدد الحواف3+4+1=8، والأسماء سبعة. نلونه بوضع C وE وG في1، وA وD وF في2، وB في3.

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

إذا اختير A وB وC جميعًا، فالمثلث باقٍ ويجبر ثلاثة ألوان. وتقييد التلوين المعلن على الأسماء المختارة لا يزال صحيحًا ويستعمل ثلاثة على الأكثر. لا زمرة أكبر من3 في الأصل أو في أي جزء منه، فـχ=ω=3.

إذا غاب واحد على الأقل من A B C، فإن ما بقي من المثلث رأس أو حافة أو لا شيء، أي لا دورة فيه. وما بقي من DEFG هو جزء من دورة زوجية يمكن تلوينه بلونين، مع مجموعتي D F وE G.

الوصلة الوحيدة بين الجزأين هي CD إذا بقي طرفاها. يمكن تبديل اسمي اللونين في جزء المثلث الباقي لتختلف ألوان C وD، دون تغيير صلاحية التلوين داخله. بقية أجزاء المثلث المنفصلة تلون بحرية؛ لذلك يقبل المستحث كله لونين.

إذا وجدت حافة في هذه الحالة، فـχ≥2 وω≥2، ولا مثلث، فتكون القيمتان2. إذا بقيت أسماء بلا حواف فالقيمتان1؛ وإذا كانت المجموعة خالية فالقيمتان0 وفق تمثيلنا. غطت الحالتان كل اختيار، لذلك هذا التحكم مثالي.

اختيار الرؤوس يلزمك بكل حوافها

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

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

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

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

حصر محدود يراجع الحجة

راجعنا جميع2^8=256 مجموعة أسماء في الأصل، و2^7=128 في التحكم. في كل حالة أبقينا كل حافة طرفاها مختاران. الأصل له سبع مجموعات تخالف المساواة، منها DEFGH، والتحكم لا حالة فشل فيه. الشاهد الواحد والحجة الشاملة هما سبب الحكم، لا عدد حالات الفشل وحده.

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

للفحص الإضافي مررنا جميع1024 قائمة حواف على خمسة أسماء، وفحصنا32 مجموعة أسماء في كل مدخل، أي1024×32=32768 حالة مستحثة. أعدنا استخدام نتيجة1100 مدخل مميز بعد تثبيت الأسماء المختصرة والحواف؛ عدد الحالات ليس عدد عمليات حساب جديدة لكل تكرار.

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

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

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