التلوين الكسري للحواف: لماذا لا يكفي تقريب القيمة؟

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

لا يكفي تقريب القيمة الكسرية إلى العدد الصحيح الأعلى للحصول على أقل ألوان الحواف. في رسم بيترسن، ست مطابقات كاملة بوزن 1/2 لكل منها تغطي كل حافة بوزن 1، فتكون الكلفة 3، وهي الأقل. لكن ثلاثة ألوان عادية مستحيلة؛ أربعة ألوان تحقق تلوينًا صحيحًا.

• المتغيرات أوزان مجموعات من الحواف المتباعدة عند الرؤوس؛ نجمع أوزان المجموعات المحتوية على كل حافة، ويجب أن تبلغ تغطيتها 1 على الأقل.
• في بيترسن، كل حافة تظهر في اثنتين من المطابقات الست، فتبلغ تغطيتها 1/2+1/2=1، والكلفة 6×1/2=3.
• ضع سعر شهادة 1/5 على كل حافة. أي مطابقة تسع خمس حواف على الأكثر، فلا يتجاوز مجموع أسعارها 1؛ مجموع الأسعار 15×1/5=3 يثبت الأقل.
• لو أمكن تلوين الحواف بثلاثة ألوان عادية، لصنعت كل فئة لون مطابقة كاملة، ولبقيت بعد حذفها دورات تتناوب فيها الفئتان الأخريان. كل مطابقة كاملة في بيترسن تترك دورتين من طول 5؛ التناوب مستحيل.
• الدورة C5 تعطي 5/2، والتلوين العادي يحتاج 3؛ نجاح التقريب هنا لا يجعله قاعدة عامة، لأن بيترسن يعطي 3 مقابل 4.
• النجمة ذات ثلاث حواف تعطي 3 للحواف و 2 للرؤوس، بينما K4 يعطي 3 للحواف و 4 للرؤوس؛ موضوع التغطية يغير المسألة.
• الرسم بلا حواف كلفته 0، ولو بقيت رؤوس معزولة؛ القيود هنا للحواف. الحصر في أربعة رؤوس لا يكشف فجوة بيترسن ذات عشرة رؤوس.

ما الذي يحمل الوزن، وما الذي تجب تغطيته؟

التلوين العادي للحواف يعطي الحواف التي تشترك في رأس ألوانًا مختلفة، ويسأل عن أقل عدد ألوان. [5]

المطابقة مجموعة حواف لا تشترك اثنتان منها في رأس. والمطابقة الكاملة تغطي جميع الرؤوس. [3]

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

صلة التعريف بالمصادر تمر برسم الحواف: رأس لكل حافة أصلية، وجوار بين رأسين إذا اشتركت حافتاهما في طرف. [2]

المجموعات المستقلة في رسم الحواف تقابل المطابقات في الرسم الأصلي؛ لذلك تتحول تغطية رؤوس رسم الحواف بالمجموعات المستقلة إلى تغطية الحواف الأصلية بالمطابقات. التعريف الكسري في رسم الحواف هو القيمة الكسرية للحواف الأصلية. [1] [4]

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

ست مطابقات كاملة تحقق الكلفة 3

نبني بيترسن من دورة خارجية A B C D E، وخمس وصلات AF BG CH DI EJ، ونجمة داخلية بالحواف FH FI GI GJ HJ. للرسم عشرة رؤوس وخمس عشرة حافة، ودرجة كل رأس 3. هذه البنية هي بناء الدورة بخطوة 1 والداخل بخطوة 2 في المصدر. [6]

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

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

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

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

أسعار الحواف تثبت أن الكلفة لا تقل عن 3

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

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

في بيترسن، ضع السعر 1/5 على كل حافة. أي مطابقة تستخدم رأسين مختلفين لكل حافة، وفي عشرة رؤوس لا تسع أكثر من خمس حواف. لذلك مجموع أسعارها لا يتجاوز 5×1/5=1.

مجموع الأسعار على الحواف الخمس عشرة 15×1/5=3. هذا يثبت أن أي تغطية كلفتها 3 على الأقل؛ وبالتغطية السابقة ذات الكلفة 3 تثبت المساواة. الحساب كسور دقيقة، ولا يعتمد على تقريب عشري.

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

لماذا تحتاج الحواف أربعة ألوان عادية؟

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

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

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

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

فحص جدول الشاهد مباشر: عند A الألوان 1،2،3؛ وعند F الألوان 3،1،4. افحص بقية الرؤوس بالطريقة نفسها. ليس المطلوب أن تظهر الألوان الأربعة عند كل رأس، بل أن تختلف الحواف التي تتلاقى عنده.

القيمة الكسرية 3 عدد صحيح أصلًا؛ تقريبها إلى الأعلى يبقي 3. ومع ذلك أقل عدد عادي 4. لذلك لا تحول التقريب الحسابي إلى طريقة مضمونة للحصول على أقل تعيين صحيح.

C5 تنجح فيها الثلاثة، والنجمة تفرق بين الرؤوس والحواف

في C5 بالحواف AB BC CD DE AE، المطابقات AB+CD وAB+DE وBC+DE وBC+AE وCD+AE صحيحة. ضع وزن 1/2 لكل منها؛ كل حافة في مجموعتين، والكلفة 5/2.

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

في C7، المطابقات السبع ذات أكبر حجم تسع ثلاث حواف، وكل حافة في ثلاث منها. وزن 1/3 لكل مطابقة يحقق تغطية 1 وكلفة 7/3. أسعار 1/3 على الحواف تثبت الحد، لأن أي مطابقة تسع ثلاث حواف على الأكثر. العادي يحتاج 3 أيضًا.

في النجمة AB AC AD، كل مطابقة لا تضم أكثر من حافة، لأن جميع الحواف عند A. يحتاج وزن تغطية كل حافة 1، فتكون الكلفة 3؛ التلوين العادي 3 كذلك. لكن تغطية الرؤوس بالمجموعات المستقلة تعطي 2: المركز وحده والأوراق معًا.

في K4، المطابقات AB+CD وAC+BD وAD+BC بوزن 1 تغطي الست بكلفة 3. السعر 1/2 لكل حافة يثبت 3، لأن المطابقة تسع حافتين. التلوين العادي للحواف 3، بينما الرؤوس تحتاج 4.

إذن لا ترتيب ثابت بين القيمة الكسرية للحواف والقيمة الكسرية للرؤوس: النجمة تزيد الأولى، وK4 يزيد الثانية. وقد تتساويان على C5 رغم اختلاف الأشياء التي نغطيها؛ مساواة نتيجة مثال لا توحد التعريفين.

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

أمثلة دقيقة، والرسم بلا حواف قيمته 0

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

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

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

على P4، يجوز جمع AB مع CD لأن الحافتين متباعدتان عند الرؤوس. وجود BC بين طرفيهما لا يمنع المطابقة العادية. شرط المطابقة المستحثة أشد، وليس قيد هذا المقال.

على C4 القيمة الكسرية 2، إذ تكفي مطابقتا الحافتين المتقابلتين بوزن 1. لا نضيف منع دورة ذات لونين كما في التلوين اللا دوري للحواف. وعلى P5 القيمة 2 أيضًا؛ منع مسار أربع حواف بلونين يخص شرطًا آخر.

ما الذي أثبته الحصر، وما الذي بقي خارج نطاقه؟

ثبتنا أربعة رؤوس A B C D والحواف الست الممكنة. إبقاء كل حافة أو حذفها يعطي 2^6=64 رسمًا مسمى. حصرنا المطابقات غير الفارغة لكل رسم؛ مجموع أعدادها 240.

في هذا الحصر، القيمة 0 في رسم واحد، 1 في 9، 2 في 27، 3 في 27. وتساوي أقل عدد ألوان الحواف العادي في جميع 64. هذا حصر في أربعة رؤوس؛ لا ينفي فجوة بيترسن ذي عشرة رؤوس.

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

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

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

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

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