قوة عدم الانتظام: لماذا تكفي الأوزان 1 و 2 و 3 للدورة الرباعية؟

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

تحتاج الدورة الرباعية حدًا 3 لأن الأوزان حتى 2 لا تعطي إلا ثلاثة مجاميع ممكنة لأربعة رؤوس، بينما التعيين 1،1،2،3 يعطي المجاميع الأربعة المختلفة 4،2،3،5.

• نضع وزنًا صحيحًا موجبًا من 1 إلى k على كل حافة، ونطلب اختلاف مجموع الأوزان عند كل رأسين مختلفين؛ نقلل k، ولا نشترط اختلاف وزني حافتين تلتقيان. [1]
• على الدورة AB BC CD DA، الأوزان AB=1 وBC=1 وCD=2 وDA=3 تعطي مجاميع A B C D بالترتيب 4،2،3،5؛ الوزن 1 يتكرر عند B، ولا يمنع ذلك نجاح المجاميع.
• كل رأس في الدورة له حافتان. إذا كان k=2، فمجموعه من {2,3,4} فقط؛ ثلاثة أعداد لا تكفي أربعة رؤوس مختلفة، فيلزم k=3 على الأقل، والشاهد يثبت الكفاية.
• تلوين الحواف الصحيح يمنع تساوي الألوان عند رأس مشترك؛ مسألة تمييز المجاميع مع هذا الشرط تضيف قيدًا إلى الأوزان، وفي الرسوم التي لها حواف يكون حدها الأدنى مساويًا أو أكبر. [2] [3]
• في الماسة AB AC AD BC CD، الأوزان 1،2،1،1،2 تعطي المجاميع 4،2،5،3، رغم أن مجموعتي القيم عند A وC كلتيهما {1,2}؛ الجمع يحسب كل حافة حتى لو تكرر وزنها.
• طرفا حافة منفردة في مكون واحد لهما المجموع نفسه، والمعزولان لهما المجموع 0، فيستحيل التمييز؛ عند غياب هذين المانعين، تعيين قوى 2 مختلفة على الحواف يثبت وجود حل، دون إثبات الحد الأدنى.
• راجعنا 25 نموذجًا و 64 رسمًا من أربعة رؤوس؛ الفحص المنفصل جرب 137340 تعيينًا في النماذج و 1946 في رسوم الأربعة رؤوس، ووافق الحدود والشواهد، ومنها 10 رسوم بلا حل و 42 بحد 2 و 12 بحد 3.

الدرجة الموزونة تجمع الأوزان، دون شرط التلوين الصحيح

قوة عدم الانتظام هي أصغر k يسمح بأوزان للحواف من 1 إلى k تعطي درجات موزونة مختلفة لجميع الرؤوس؛ الدرجة الموزونة هي مجموع أوزان الحواف الملتقية بالرأس. [1]

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

نكتب Q[A] لمجموع الأوزان عند A. ليست هناك قيمة مستقلة نضيفها للرأس نفسه، ولا نجمع أرقام أسماء الجيران؛ نجمع أوزان حوافه، كل حافة مرة.

نقلل حد الأوزان k، ونعد القيم المستخدمة كلًا على حدة. لا يشترط استعمال جميع الأرقام حتى k، لكن تغيير قيمة وزن قد يغير المجاميع؛ لا نختزل التبديلات العددية إلى أسماء ألوان.

سنختار k عددًا صحيحًا موجبًا، حتى في حالة الرأس الوحيد بلا حواف: التعيين فارغ، ومجموعه 0، وأقل حد موجب وفق هذا الاصطلاح هو 1. نصرح بالاصطلاح بدل نقل جواب 0 من تعريف آخر.

الدورة الرباعية: وزن 1 على حافتين متلاقيتين، وأربعة مجاميع مختلفة

خذ دورة بأربع حواف AB BC CD DA. نعطي AB=1 وBC=1 وCD=2 وDA=3، دون إضافة قطر أو رأس آخر.

عند A تلتقي AB وDA، فيكون Q[A]=1+3=4. وعند B تلتقي AB وBC، فيكون Q[B]=1+1=2؛ نجمع الواحدين، ولا نحذف أحدهما.

عند C نجد Q[C]=1+2=3، وعند D نجد Q[D]=2+3=5. إذن مجاميع A B C D هي 4،2،3،5، وكلها مختلفة.

أعلى وزن حافة هو 3، لكن مجموع D يساوي 5؛ حد k يخص أوزان الحواف، ولا يحد المجاميع بالعدد نفسه.

الحافتان AB وBC لهما الوزن 1 وتلتقيان عند B. هذا لا يجعل الشاهد فاشلًا هنا، لكنه يجعله غير صالح كتلوين صحيح للحواف.

القيم المستخدمة هي {1,2,3}، وعددها ثلاثة. الشاهد يثبت أن حد 3 يكفي؛ لنثبت أنه الأقل نحتاج استبعاد كل تعيين بحد أصغر، لا اختبار ترتيب واحد.

عند الحد 2، ثلاثة مجاميع ممكنة لا تكفي أربعة رؤوس

كل رأس في هذه الدورة له حافتان. إذا سمحنا للوزن أن يكون 1 أو 2، فالمجموع إما 1+1=2، أو 1+2=3، أو 2+2=4.

الأعداد الممكنة هي {2,3,4}: ثلاثة فقط. المطلوب أربعة رؤوس بمجاميع مختلفة، ولا يمكن وضع أربعة رؤوس في ثلاث قيم دون تكرار واحدة منها.

لذلك لا يوجد أي تعيين ناجح بحد k=2، مهما بدلت مواضع الأوزان؛ حد 1 مستبعد أيضًا، إذ يعطي المجموع 2 عند الرؤوس الأربعة.

الشاهد 1،1،2،3 بحد 3 يحقق المطلوب، وقد استبعدنا كل حد أصغر؛ فتكون قوة عدم الانتظام للدورة الرباعية 3.

البرهان يعتمد على عدد المجاميع الممكنة عند درجة 2، وليس على منع تكرار الأوزان. ولا يعمم هذا الجواب تلقائيًا على جميع الدورات أو الرسوم.

إضافة شرط اختلاف الحواف المتلاقية قد ترفع الحد الأدنى

في تلوين الحواف الصحيح، تختلف ألوان أي حافتين تلتقيان عند رأس. وفي تمييز الرؤوس بمجموع أرقام الحواف مع التلوين الصحيح، نطلب هذا القيد مع اختلاف كل المجاميع. [2] [3]

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

على الدورة الرباعية، حد الأوزان 3 يكفي بالشاهد AB=1 وBC=1 وCD=2 وDA=3، لكنه يفشل شرط التلوين الصحيح عند B.

مع الشرط الإضافي، الحد الأدنى للدورة هو 4 في حصرنا: الشاهد AB=1 وBC=2 وCD=4 وDA=3 يعطي المجاميع 4،3،6،7، وتختلف الحواف المتلاقية.

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

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

في الماسة، مجموعة {1,2} نفسها قد تعطي المجموع 4 أو 5

الماسة هنا رسم بأربعة رؤوس وحواف AB AC AD BC CD؛ هي مثلثان يشتركان بالحافة AC، ولا توجد حافة BD.

أعط AB=1 وAC=2 وAD=1 وBC=1 وCD=2. عند A الأوزان 1 و 2 و 1، فيكون Q[A]=1+2+1=4؛ وعند C الأوزان 2 و 1 و 2، فيكون Q[C]=2+1+2=5.

وعند B نجد Q[B]=1+1=2، وعند D نجد Q[D]=1+2=3. المجاميع A B C D هي 4،2،5،3؛ كل رأس مميز بحد k=2.

لكن مجموعة القيم التي ظهرت عند A هي {1,2}، وكذلك عند C. المجموعة تحذف تكرار القيمة، أما جمع أوزان الحواف فيحتفظ بعدد مرات ظهورها.

لو جمعت عناصر {1,2} مرة واحدة عند كل منهما لحصلت على 3 و 3، وهي ليست المجاميع الحقيقية؛ الفرق بين 4 و 5 جاء من تكرار 1 عند A وتكرار 2 عند C.

بحد 1، مجموع A وC يساوي 3، ومجموع B وD يساوي 2، فلا ينجح التمييز. الشاهد بحد 2 يثبت أنه الحد الأدنى، حتى مع تساوي مجموعتي القيم.

الموانع تخص مجاميع الرؤوس، وقوى 2 تعطي شاهد وجود

حافة تشكل مكونًا وحدها تجعل مجموع طرفيها مساويًا لوزنها نفسه. ورأسان معزولان مجموع كل منهما 0؛ نعد وجود إحدى الحالتين مانعًا للحل. [1]

معزول واحد لا يمنع الحل وحده: مجموعه 0، وكل رأس له حافة واحدة على الأقل له مجموع موجب. وفي الرأس الوحيد، لا يوجد زوج رؤوس يحتاج إلى التمييز.

عند غياب المانعين، أعط كل حافة قوة مختلفة من قوى 2: 1 و 2 و 4 و 8، ثم تابع حسب عدد الحواف. مجموع القوى المختلفة يحدد حواف الرأس تحديدًا وحيدًا.

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

على الدورة AB BC CD DA، الأوزان 1،2،4،8 تعطي مجاميع A B C D بالأرقام 9،3،6،12. هذا حل بحد 8، بينما عرفنا حلًا بحد 3؛ شاهد الوجود لا يكفي لإعلان أقل حد.

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

حصر عددي يحتفظ بتكرار الأوزان، ويقارن جميع الرؤوس

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

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

فحص منفصل بطريقة حاصل الضرب جرب 137340 تعيينًا عبر الحدود المختبرة، ومنها 1379 تعطي مجاميع مختلفة لجميع الرؤوس؛ 521 منها تحقق شرط التلوين الصحيح أيضًا، وهو تشخيص إضافي لا شرط قبول هنا.

في أربعة رؤوس، ست حواف ممكنة تنتج 64 رسمًا مسمى. عشرة بلا حل، و 42 أقل حد لها 2، و 12 أقل حد لها 3؛ العدد الكلي 64.

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

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

الأمثلة والبراهين والحصر من إعداد المقال بعد قراءة التعريف. كلا الفحصين يستعمل Python؛ لا ندعي مراجعة بشرية مستقلة أو صيغة لجميع عائلات الرسوم.