التلوين الكلي بالجداء يميز الرؤوس المتجاورة بحاصل ضرب عدد الرأس وأعداد حوافه، مع الحفاظ على التلوين الصحيح. تغيير العملية من الجمع إلى الضرب قد يغير نجاح التعيين نفسه: في مثلثنا تنجح الجداءات 15،24،60، بينما تفشل المجاميع 9،9،12. سنحسب النتيجتين، ونوضح دور العامل المشترك وحدود الأعداد وتبديل أسمائها.
الخلاصة السريعة
ينجح الضرب في شاهد المثلث لأن الأعداد A=1 وB=2 وC=3 مع AB=3 وBC=4 وCA=5 تعطي الجداءات 15،24،60 المختلفة، بينما تعطي المجاميع 9،9،12 فتفشل الحافة AB.
- نعين أعدادًا صحيحة موجبة من 1 إلى k للرؤوس والحواف في تلوين كلي صحيح، ونطلب اختلاف حاصل ضرب عدد الرأس وأعداد حوافه عند طرفي كل حافة، ثم نقلل k. [1]
- الشاهد A=1 وB=2 وC=3 مع AB=3 وBC=4 وCA=5 صحيح كليًا، وجداؤه عند كل رأس هو 15 و 24 و 60 على الترتيب؛ الحد 5 يخص الأعداد المعينة، لا النواتج.
- جمع الأعداد في الشاهد نفسه يعطي 9،9،12، فتفشل AB؛ نجاح الضرب لا يعني نجاح الجمع، حتى لو اتفق الحد الأدنى للمسألتين في الأمثلة المختبرة.
- عامل الحافة المشتركة موجب، فيمكن إلغاؤه عند اختبار تساوي جداءي طرفيها؛ وتبديل أسماء داخل اللوحة من 1 إلى 6 قد يحافظ على الصحة الكلية وعلى خمس قيم مستخدمة، لكنه يعطي 24،24،72 ويفشل على AB.
- للمثلث الحد الأدنى بالجداء 5: الحد 3 يعطي 6 تلوينات صحيحة والحد 4 يعطي 96، ولا ينجح أي منها؛ عند 5 توجد 780 تلوينًا صحيحًا، منها 360 يميز الجداءات و 288 من هذه يميز المجاميع أيضًا.
- الأعداد الأولية المختلفة على كل الرؤوس والحواف تعطي شاهد وجود لأي رسم بسيط؛ المعزول جداؤه عدد نفسه لأن جداء الحواف الفارغ 1، ويمكن تكرار جداء غير المتجاورين؛ المسار P3 يقبل 3،6،3 بحد 3، والرسم الخالي من الحواف حدّه الموجب 1.
- راجعنا 10 نماذج و 64 رسمًا من أربعة رؤوس بطريقتين؛ الفحص المنفصل جرب 13300636 تعيينًا للنماذج و 26072442 للرسوم، ووافق الحدود والشواهد؛ توزيع حدود الرسوم واحد بحد 1 و 21 بحد 3 و 31 بحد 4 و 11 بحد 5.
نضرب عدد الرأس في أعداد حوافه، مع ثلاثة شروط للصحة الكلية
يعرف المصدر التلوين الكلي المميز بالجداء بأعداد من 1 إلى k على الرؤوس والحواف: نضرب عدد الرأس في أعداد الحواف الملتقية به، ونطلب اختلاف الناتجين عند كل رأسين متجاورين؛ نقلل k. [1]
الصحة الكلية تلزم باختلاف عددي الرأسين المتجاورين، واختلاف عددي الحافتين المتلاقيتين، واختلاف عدد الرأس عن عدد كل حافة ملتقية به. [2]
نفترض رسمًا بسيطًا غير موجه، فيه رأس واحد على الأقل. نكتب P[A] للناتج عند A، ونفحص P[u]≠P[v] لكل حافة uv أصلية؛ لا نقارن رأسين غير متجاورين أو من مكونين منفصلين.
لا ندخل أعداد الرؤوس المجاورة في ضرب A، ولا نستبدل عوامل الضرب بمجموعة أسماء ألوان. كل عنصر معين له عدد، والجداء ناتج محسوب قد يتجاوز k.
نبحث عن أصغر حد موجب k، وليس عدد القيم المستخدمة هدفًا مستقلًا. نختبر الأعداد الفعلية؛ حذف تبديلات أسمائها دون حساب قد يحذف حالة مختلفة عدديًا.
الأعداد نفسها تعطي الجداءات 15،24،60 على المثلث
المثلث له الحواف AB BC CA. نعطي الرؤوس A=1 وB=2 وC=3، والحواف AB=3 وBC=4 وCA=5.
أعداد الرؤوس مختلفة، وأعداد الحواف مختلفة. الحافة AB بالعدد 3 تختلف عن طرفيها 1 و 2؛ BC بالعدد 4 تختلف عن 2 و 3؛ CA بالعدد 5 تختلف عن 3 و 1، فيصح التلوين الكلي.
العدد 3 على C وعلى AB مسموح لأن C ليس طرفًا للحافة AB؛ شروط الصحة لا تفرض اختلاف جميع العناصر في الرسم.
نحسب P[A]=1×3×5=15، وP[B]=2×3×4=24، وP[C]=3×4×5=60. الحواف AB وBC وCA تصل جداءات مختلفة، فينجح الشاهد.
أكبر عدد معين هو 5، أما الناتج 60 فهو حاصل ضرب، فلا يخرق الحد. هذا يثبت كفاية 5، ثم نفحص الحدود الأصغر لإثبات أنه الأقل.
الجمع يفشل على AB رغم بقاء التلوين الكلي صحيحًا
في التلوين الكلي المميز بالمجاميع، نجمع عدد الرأس وأعداد حوافه الملتقية، ونطلب اختلاف المجموعين عند كل رأسين متجاورين، مع التلوين الكلي الصحيح وبأعداد من 1 إلى k. [3]
نستخدم التعيين نفسه دون تغيير أي عدد. الجمع عند A هو 1+3+5=9، وعند B هو 2+3+4=9، وعند C هو 3+4+5=12. إذن AB تفشل في شرط المجاميع.
في الضرب، الزوج الذي تساوى بالجمع هو 1×5=5 مقابل 2×4=8 بعد إلغاء العامل 3 المشترك؛ لذلك اختلف الناتجان 15 و 24. اختلاف العملية هو الذي غير الفحص، لا تغيير الألوان.
للمثلث كانت مسألة المجاميع تحتاج الحد 5 أيضًا في الحصر السابق. اتفاق الحد لا يجعل شروط قبول التعيينات واحدة: عند الحد 5 توجد 360 حالة جداء ناجحة، ومنها 288 تحقق شرط المجاميع أيضًا.
في رسوم الأربعة رؤوس الـ64 اتفقت الحدود الدنيا للجداء والمجموع في الحصر الذي أجريناه. هذه ملاحظة على الرسوم المختبرة، ولا نعلن مساواة عامة لكل الرسوم أو لكل تعيين.
| الرأس | الجداء | المجموع |
|---|---|---|
| A | 15 | 9 |
| B | 24 | 9 |
| C | 60 | 12 |
نلغي عامل الحافة الموجب، لكن لا نلغي أثر أسماء الأعداد
عند طرفي AB، يظهر عدد الحافة AB عاملًا في الجداءين. لأنه موجب، يتساوى الجداءان إذا وفقط إذا تساوى حاصل ضرب العوامل الباقية عند الطرفين.
في شاهدنا، نقارن 1×5=5 مع 2×4=8 بعد إلغاء عامل AB=3. هذا اختبار لتساوي الجداءين، وليس حذفًا للحافة من الرسم أو من شروط التلوين الصحيح.
لرؤية أثر أسماء الأعداد، ننظر إلى الشاهد داخل اللوحة من 1 إلى 6، ثم نبدل 3 مع 4، و 5 مع 6، ونبقي 1 و 2. هذا تبديل واحد يطبق على كل العناصر.
تصبح الرؤوس A=1 وB=2 وC=4، والحواف AB=4 وBC=3 وCA=6. يظل التلوين صحيحًا كليًا ويستخدم خمس قيم مختلفة، كما كان الشاهد الأصلي.
لكن الجداءات الآن هي 24،24،72. بعد إلغاء عامل AB=4، نجد 1×6=2×3=6، فتفشل AB. لذا لا يكفي عدد القيم المستخدمة ولا نمط مساواتها لتقرير نجاح الضرب.
لا يثبت هذا المثال حدًا أدنى 6. هو تعيين داخل اللوحة من 1 إلى 6 يوضح أثر تبديل الأعداد؛ الشاهد الأصلي ينجح حتى بحد 5.
المثلث يحتاج حدًا 5، بينما تلوينه الكلي العادي يحتاج 3
تجاور رؤوس المثلث يفرض ثلاثة أعداد مختلفة، فيستبعد الحدين 1 و 2. عند الحد 3 توجد ستة تلوينات كلية صحيحة؛ لا يميز أي منها الجداءات.
مثال الحد 3 هو A=1 وB=2 وC=3 مع AB=3 وBC=1 وCA=2. الجداء عند كل رأس هو 6، فتفشل الحواف الثلاث، رغم صحة التلوين الكلي.
عند الحد 4 توجد 96 حالة صحيحة كليًا، ولا تميز أي منها جداءات الجيران. الحصر يشمل الحالات التي لا تستخدم 4، لأن الأعداد المسموحة من 1 إلى 4.
عند الحد 5 توجد 780 حالة صحيحة كليًا، ومنها 360 تميز الجداءات. هذه أعداد تعيينات مسماة بأعدادها الفعلية؛ لا نقسمها على تبديلات الأسماء.
استبعاد كل الحدود الموجبة الأصغر مع الشاهد الناجح يثبت الحد الأدنى 5. أما التلوين الكلي العادي للمثلث فحده 3، بالشاهد الصحيح المذكور، دون طلب اختلاف الجداءات.
| الحد الموجب | صحيح كليًا | يميز جداءات الجيران | من حالات الجداء: يميز المجاميع أيضًا |
|---|---|---|---|
| 1 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 |
| 3 | 6 | 0 | 0 |
| 4 | 96 | 0 | 0 |
| 5 | 780 | 360 | 288 |
الأعداد الأولية تميز الجداءات، والمعزول يضرب عدد نفسه في 1
نعطي كل رأس وحافة عددًا أوليًا مختلفًا. اختلاف أعداد كل العناصر يحقق شروط الصحة الكلية، وإن لم يكن أصغر تعيين ممكن.
تحليل عدد إلى عوامله الأولية يحدد العوامل الأولية المختلفة التي ضربناها. جداء رأس u يشمل العدد الأولي المخصص لـu، بينما جداء رأس v مختلف عنه لا يشمل ذلك العامل؛ لذا الناتجان مختلفان.
هذا الشاهد يميز جميع الرؤوس، فيميز الجيران أيضًا. نستخدمه لإثبات وجود حل لكل رسم بسيط، لا لإثبات أقل حد أو حد ثابت لجميع الرسوم.
نعتمد جداء المجموعة الفارغة 1؛ لذلك جداء المعزول هو عدد نفسه مضروبًا في 1، أي عدد نفسه. أي عدد من المعزولين مسموح؛ لا توجد حافة تفرض مقارنة بينهم.
على المسار P3 بحواف AB BC، التعيين A=1 وB=2 وC=3 مع AB=3 وBC=1 يعطي الجداءات 3،6،3، فينجح على الحافتين؛ لا توجد حافة AC، فيسمح بتساوي الطرفين.
الحافتان عند B مع الرأس B تحتاج ثلاثة أعداد مختلفة، فيثبت الحد الأدنى للمسار 3. الحافة المنفردة أيضًا تقبل حدًا 3 بالتعيين A=1 وB=2 وAB=3، والناتجان 3 و 6.
في الرسم الخالي من الحواف نعطي كل الرؤوس العدد 1، فتكون الجداءات كلها 1 دون مقارنات. وفق اصطلاح الحد الموجب، الحد الأدنى 1.
فحص مستقل يقارن الضرب والجمع دون خلط شروط القبول
جدول النماذج يعرض الحد الأدنى للجداء والحد السابق للمجموع، ثم أعداد الرؤوس والحواف في شاهد الجداء. لا نفترض أن شاهد أحدهما ينجح للآخر.
راجعنا 10 نماذج و 64 رسمًا مسمى من أربعة رؤوس، من الحواف الست الممكنة. جربنا كل حد من 1 حتى أول نجاح، مع شروط التلوين الكلي الثلاثة قبل مقارنة الجداءات على الحواف الأصلية.
الطريقة الأولى تستبعد مخالفة التلوين الصحيح أثناء بناء التعيين. الفحص المنفصل يجرب بالفعل كل التعيينات العددية بعداد مستقل، دون حذف تبديلات أسماء الأعداد.
في النماذج، جرب الفحص المنفصل 13300636 تعيينًا؛ 6217 صحيح كليًا، و 3579 منها يميز جداءات الجيران، و 2925 من الأخيرة يميز المجاميع أيضًا، و 3086 من حالات الجداء يميز جميع الرؤوس بالجداء.
في رسوم الأربعة رؤوس، جرب 26072442 تعيينًا؛ 49441 صحيح كليًا، و 24025 منها يميز جداءات الجيران، و 18817 من الأخيرة يميز المجاميع أيضًا، و 20904 من حالات الجداء يميز جميع الرؤوس بالجداء.
توزيع حدود الجداء في الرسوم الـ64 هو: واحد بحد 1، و 21 بحد 3، و 31 بحد 4، و 11 بحد 5؛ كلها ممكنة. اختبارات الجمع وجميع الرؤوس تشخيص إضافي، ولا نضيفها إلى شرط قبول الجداء.
وافق الفحص المنفصل الحدود والشواهد وعدد القيم المستخدمة وأعداد التعيينات، وراجعنا الأعداد الأولية والمعزولين وتبديل الأسماء. تستخدم الطريقة الأولى Python والثانية Node؛ لا ندعي مراجعًا بشريًا أو خبيرًا مستقلًا أو صيغة عامة لكل عائلة.
| النموذج | حد الجداء | حد المجموع | أعداد الرؤوس | أعداد الحواف |
|---|---|---|---|---|
| مثلث C3 | 5 | 5 | A=1؛ B=2؛ C=3 | AB=3؛ BC=4؛ CA=5 |
| دورة C4 | 4 | 4 | A=1؛ B=2؛ C=1؛ D=2 | AB=3؛ BC=4؛ CD=3؛ DA=4 |
| مسار P3 | 3 | 3 | A=1؛ B=2؛ C=3 | AB=3؛ BC=1 |
| مسار P4 | 4 | 4 | A=1؛ B=2؛ C=1؛ D=2 | AB=3؛ BC=4؛ CD=3 |
| نجمة بثلاث أوراق | 4 | 4 | A=1؛ B=2؛ C=2؛ D=3 | AB=3؛ AC=4؛ AD=2 |
| رسم كامل K4 | 5 | 5 | A=1؛ B=2؛ C=3؛ D=4 | AB=3؛ AC=4؛ AD=5؛ BC=5؛ BD=1؛ CD=2 |
| ماسة: مثلثان يشتركان بحافة | 5 | 5 | A=1؛ B=2؛ C=3؛ D=2 | AB=3؛ AC=2؛ AD=4؛ BC=1؛ CD=5 |
| أربعة رؤوس بلا حواف | 1 | 1 | A=1؛ B=1؛ C=1؛ D=1 | تعيين فارغ |
| حافة ورأسان معزولان | 3 | 3 | A=1؛ B=2؛ C=1؛ D=1 | AB=3 |
| مساران P3 منفصلان | 3 | 3 | A=1؛ B=2؛ C=3؛ D=1؛ E=2؛ F=3 | AB=3؛ BC=1؛ DE=3؛ EF=1 |
اقرأ أيضًا: استرجاع الرسوم البيانية: نوع العلاقة واتجاهها
اقرأ أيضًا: أنواع الرسم البياني: اختر الشكل الذي يجيب عن السؤال
المراجع
- Neighbor product distinguishing total colorings of corona of subcubic graphs — arXiv:2011.10455
- MathWorld — Total Chromatic Number
- Asymptotically optimal neighbour sum distinguishing total colourings — arXiv:1508.01062
أُعدّ هذا المقال بمساعدة الذكاء الاصطناعي، وخضع لمراجعة ذاتية بالأداة نفسها. لا يُنسب إلى مراجع بشري أو خبير مستقل. منهجية المحتوى.