تمييز الجيران بضرب أرقام الحواف: لماذا يحتاج المسار الرقم 2؟

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

يحتاج مسار ثلاثة رؤوس حدًا مسموحًا قدره 2 لأن الحافتين بالرقم 2 تعطيان المنتجات 2 و 4 و 2 المختلفة عند الطرفين المتجاورين، بينما الرقم 1 وحده يعطي المنتج 1 عند الجميع.

• نسند لكل حافة عددًا صحيحًا من 1 إلى k، ونضرب الأرقام عند الرأس، ونقارن طرفَي كل حافة؛ الحد المطلوب هو أصغر k يسمح بذلك. [1]
• شاهد P3 هو AB=2 وBC=2، ومنتجاته 2،4،2؛ الحد الأدنى 2 رغم استخدام قيمة عددية واحدة فقط، وتساوي الطرفين غير المتجاورين مسموح.
• الجمع يقبل P3 بالحافتين 1،1 لأن المجاميع 1،2،1، لكن الضرب يفشل بمنتجات 1،1،1؛ وتبديل الاسمين 1 و 2 يحول الشاهد الضربي الناجح إلى الفاشل.
• تحت الرقمين 1 و 2، المنتج هو 2^t حيث t عدد الحواف الملتقية بالرأس التي تحمل 2؛ نعد هذه الحواف، لا درجة الرأس ولا عدد أسماء ألوانه.
• مكون الحافة الوحيدة يمنع الحل، أما أي عدد من المعزولين فلا يمنعه؛ عند غياب ذلك المكون تثبت أعداد أولية مختلفة للحواف وجود حل، ولا تثبت أقل حد.
• في المثلث، إلغاء العوامل الموجبة المشتركة يفرض ثلاثة أرقام مختلفة للحواف؛ الشاهد 1،2،3 يعطي المنتجات 3،2،6، فيثبت الحد 3.
• وافق فحصان لكل التعيينات العددية الحدود والشواهد في 25 نموذجًا و 64 رسمًا من أربعة رؤوس؛ فيها 9 مستحيلة وواحدة حدها 1 و 49 حدها 2 و 5 حدها 3، دون تعميم الحصر.

نضرب أرقام الحواف ونقلل الحد المسموح لها

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

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

نكتب P[A] لحاصل الضرب عند A. ندخل رقم كل حافة ملتقية به مرة، بما في ذلك الأرقام المكررة؛ الحافة المشتركة تدخل في حساب كل طرف.

نطلب P[u]≠P[v] إذا كانت uv حافة أصلية. لا نقارن كل رأسين مختلفين، ولا نضيف حافة بين غير المتجاورين. هذا اختلاف للمنتجات عند الرؤوس، وليس شرطًا على تساوي أرقام حافتين متلاقيتين.

اللوحة هنا 1..k كلها أعداد مسموحة، ولا يلزم استعمالها جميعًا. نقلل أعلى رقم مسموح k، ولا نقلل عدد القيم المختلفة المستخدمة كما نفعل مع أسماء الألوان الرمزية.

مسار ثلاثة رؤوس يقبل الحافتين 2،2 والحد الأدنى له 2

خذ P3 بالرؤوس A B C والحافتين AB BC. أعط AB=2 وBC=2؛ عند A توجد حافة واحدة، فيكون P[A]=2، وعند B حافتان فيكون P[B]=2×2=4، وعند C يكون P[C]=2.

على AB يختلف 2 عن 4، وعلى BC يختلف 4 عن 2، فتنجح المقارنتان. تساوي P[A] وP[C] مقبول لأن AC ليست حافة؛ لا نطلب تمييز جميع الرؤوس.

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

تحت k=2، التعيينات الأربعة هي 1،1 و 1،2 و 2،1 و 2،2. الأول يفشل عند الحافتين، والثاني عند BC، والثالث عند AB، ولا ينجح إلا الرابع.

استعملنا قيمة عددية واحدة هي 2، لكن حد اللوحة هو 2؛ لا يصبح الحد 1 بسبب عدد القيم المستخدمة. وجود عامل 2 في حافتَي الوسط يرفع منتجه إلى 4، وليس إلى اسم لون جديد.

تلوين الحواف الصحيح يشترط اختلاف لونَي أي حافتين تلتقيان عند رأس. [2]

الشاهد يكرر الرقم 2 عند B، فلا يكون صحيحًا بهذا المعنى، لكنه مقبول في المسألة الضربية. لا نحذف هذا التعيين من البحث بسبب تساوي رقمَي حافتين.

الضرب يختلف عن الجمع وتبديل أسماء الألوان

الوسم الجمعي للحواف يحسب مجموع الأعداد الملتقية بالرأس، ويطلب اختلاف المجاميع عند الرأسين المتجاورين. [3]

في P3 بالحافتين 1،1، المجاميع عند A وB وC هي 1،2،1، فتختلف عند كل حافة. أما المنتجات فهي 1،1،1، فتفشل الحافتان؛ لا ننقل حكم الجمع إلى الضرب.

نعكس التشخيص في رسم كامل K4 بالحواف AB AC AD BC BD CD والأرقام 1،1،2،3،1،2. المنتجات عند A وB وC وD هي 2،3،6،4، وهي مختلفة كلها، فتنجح المقارنات الست.

المجاميع في التعيين نفسه هي 4،5،6،5؛ يتساوى B مع D وهما متجاوران، فيفشل الجمع عند BD رغم نجاح الضرب. الجدول يحسب الحالتين من الأرقام نفسها.

لو بدلنا 1 و 2 تبديلًا متقابلًا في لوحة P3 الناجحة، تحولت الحافتان 2،2 إلى 1،1. تدمر المنتجات الجديدة التمييز؛ الأعداد ليست أسماء ألوان يمكن إعادة تسميتها بحرية.

لهذا نختبر التعيينات العددية نفسها، ولا نوحدها بترتيب أول ظهور الاسم. التعيين 2،2 لا يكافئ 1،1، ولو كان كل منهما يستعمل قيمة مختلفة واحدة.

المجموعة المتعددة تحتفظ بتكرار الأرقام، بينما الضرب قد يخفي بعض المعلومات: ⟨1,2⟩ و⟨2⟩ مختلفتان لكن منتجهما 2. هذا مثال حسابي على حذف العامل 1، لا شاهد رسم إضافي غير محسوب.

الرقم 1 لا يغير المنتج ونعد الحواف التي تحمل 2

تحت k=2، كل عامل إما 1 أو 2. إذا حملت t حواف عند رأس الرقم 2، وكان الباقي 1، فإن حاصل الضرب P=2^t. عندما t=0 يكون المنتج 1.

إذن يختلف منتجا طرفَي حافة تحت هذه اللوحة إذا وفقط إذا اختلف عدد الحواف التي تحمل 2 عند الطرفين. لا نساوي t بدرجة الرأس، لأن عوامل 1 لا تغير المنتج.

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

في دورة C4 بالحواف AB BC CD DA، أعط الأرقام 1،1،2،2. المنتجات عند A وB وC وD هي 2،1،2،4؛ كل حافة تصل قيمتين مختلفتين، فينجح حد 2.

الحد 1 يفشل في كل رسم له حافة، لأنه يجعل المنتجات كلها 1؛ لذلك تثبت لوحة C4 السابقة حدها الأدنى 2. تساوي منتجَي A وC لا يضر لأنهما غير متجاورين.

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

الحافة الوحيدة تمنع الحل والمعزولات لا تمنعه

يسجل المصدر مكون K2، المكون ذو رأسين وحافة واحدة، عائقًا لوجود الوسم المطلوب. [1]

إذا كان هذا المكون هو AB ورقم الحافة c، كان P[A]=c وP[B]=c دائمًا. لا يمكن تغيير رقم الحافة وحده لتمييز طرفيها، مهما رفعنا الحد المسموح.

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

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

للرسم غير الفارغ بلا حواف حد موجب 1 حسب تعريف اللوحة، والتعيين للحواف فارغ. لا نحوله إلى الحد صفر بسبب عدم استخدام أرقام على حواف.

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

في رسم بسيط، الحافة المشتركة الوحيدة الممكنة بين الرأسين هي uv. إذا تطابقت الحواف كلها، لم تكن عند أي منهما حافة أخرى، فيشكلان مكون K2 الذي استبعدناه؛ إذن تختلف المنتجات عند كل حافة.

البناء يثبت وجود حل، لا أقل حد. في P3 يمكن أخذ العددين الأوليين 2 و 3، فتكون المنتجات 2،6،3 وحد اللوحة 3، بينما الشاهد 2،2 يحقق حدًا أصغر قدره 2.

المثلث يحتاج ثلاثة أرقام مختلفة للحواف

خذ C3 بالحواف AB BC CA، وأعطها أعدادًا موجبة x وy وz على الترتيب. المنتجات عند A وB وC هي xz وxy وyz.

مقارنة A وB تعطي xz≠xy، وهي تكافئ z≠y لأن x موجب ويمكن إلغاؤه. مقارنة B وC تكافئ x≠z، ومقارنة C وA تكافئ y≠x.

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

الحواف بالأرقام 1،2،3 تعطي P[A]=3 وP[B]=2 وP[C]=6، وهي مختلفة كلها. يثبت ذلك الحد الأدنى 3 للمثلث.

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

نحصي كل التعيينات العددية دون اختزال أسماء الألوان

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

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

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

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

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

في رسوم الأربعة، يوجد 9 مستحيلة بسبب مكون K2، ورسم واحد حده 1 بلا حواف، و 49 حدها 2، و 5 حدها 3. المعزولات وحدها ليست سبب الاستحالة.

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