التلوين الكسري: كيف تبلغ قيمة الدورة الخماسية 5/2؟

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

لأن خمسة أزواج مستقلة، وزن كل منها 1/2، تغطي كل رأس في الدورة مرتين، فتبلغ تغطيته 1 بكلفة 5/2؛ ولا يمكن كلفة أقل لأن كل مجموعة مستقلة تضم رأسين على الأكثر.

• التلوين الكسري يعطي المجموعات المستقلة أوزانًا حقيقية غير سالبة، بحيث تبلغ تغطية كل رأس 1 على الأقل؛ العدد اللوني الكسري أقل مجموع لهذه الأوزان. [1] النطاق رسم محدود وبسيط وغير موجه وغير فارغ الرؤوس؛ نغطي الجميع حتى المعزول. الهدف مجموع الأوزان، وليس عدد أسماء الألوان أو تقريب عدد صحيح. المجموعات هنا مجموعات رؤوس، وليست حواف المطابقة الكسرية.
• على C5 بالحواف AB BC CD DE AE، الأزواج AC AD BD BE CE مستقلة. إعطاء كل زوج 1/2 يغطي كل رأس 1، ومجموع الخمسة 5/2. أي مجموعة مستقلة تسع رأسين فقط، فتغطية الخمسة تفرض كلفة لا تقل عن 5/2. التلوين الصحيح يحتاج 3، بالشاهد 12123؛ إغلاق الدورة يمنع التناوب بلونين.
• للحد الأدنى، أعط الرؤوس أوزانًا غير سالبة y، بشرط ألا يتجاوز مجموعها داخل أي مجموعة مستقلة 1. مجموع y لا يتجاوز كلفة أي تغطية؛ مساواته لكلفة شاهد ناجح تثبت الأقل. في C5 أعط كل رأس 1/2. هذا فحص بقيود جميع المجموعات، لا افتراض حد أدنى من شاهد تغطية وحده.
• التلوين الصحيح يعطي تغطية بوزن 1 لكل فئة. [2] حد n/alpha أدنى، حيث alpha أكبر حجم مستقل. [4] النجمة بثلاث أوراق قيمتها 2 لا 4/3، والماسة 3 لا 2. مثلث مع حافة منفصلة قيمته 3 رغم n/alpha=5/2؛ ومع معزولين قيمته 3 رغم 5/3. لا يلزم أن يساوي الحد القيمة.
• في الاتحاد المنفصل، القيمة أكبر قيمة للمكونات، لا مجموعها؛ يمكن دمج تغطياتها في مجموعات مستقلة مشتركة. المثلث والحافة يحتاجان 3 لا 5. المعزول لا يضاف إلى الكلفة، لكنه يبقى داخل التغطية. الرسم بلا حواف يقبل المجموعة كلها بوزن 1، وقيمته 1 لا 0؛ المجموعة الفارغة لا تغطي رأسًا.
• C7 قيمتها 7/3: سبع مجموعات مستقلة من 3، كل منها بوزن 1/3، تغطي كل رأس ثلاث مرات؛ أوزان رؤوس 1/3 تثبت الأقل، والصحيح 3. K_n قيمتها n لأن كل مجموعة مستقلة منفردة. أي رسم ثنائي الأجزاء فيه حافة قيمته 2، بما فيه P4 وP5 وP6 وP7 والنجمتان وC4 وC6 وK2,3 وK3,3؛ الخالي استثناء قيمته 1. K4 وK5 وK6 وK7 قيمها 4 و 5 و 6 و 7، والماسة 3.
• راجعنا 23 مثالًا و 64 رسمًا رباعيًا بشهادات تغطية وحد أدنى متساويتين باستخدام كسور دقيقة، وفحص آخر بالتمثيل الثنائي راجع كل المجموعات المستقلة والقيود وتغطية المعزولات. في الأربعة تساوي القيمة العدد الصحيح: 1 في رسم، 2 في 40، 3 في 22، 4 في رسم؛ فُحص 481 قيدًا لمجموعة غير فارغة. C5 وC7 خارج الحصر تنفيان تعميم المساواة. راجعنا رأسًا ورسمَي رأسين؛ مولد التقسيمات والحساب الكسري مشتركان، ولا ندعي محللًا عامًا للبرمجة الخطية أو مراجعة بشرية.

الكلفة مجموع أوزان مجموعات مستقلة

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

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

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

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

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

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

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

خمسة أزواج تغطي C5 مرتين بنصف وزن

ثبت A B C D E والحواف AB BC CD DE AE. الأزواج AC AD BD BE CE لا يحتوي أي منها حافة أصلية، فهي مستقلة. لا نرسم حواف جديدة بين أطراف الأزواج؛ الزوج اسم مجموعة فقط.

أعط كل زوج وزن 1/2. A في AC وAD، وB في BD وBE، وC في AC وCE، وD في AD وBD، وE في BE وCE. كل رأس يرى مجموع 1/2+1/2=1، فتنجح التغطية.

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

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

مجموع تغطيات الرؤوس الخمسة لا يقل عن 5. كل وزن على مجموعة مستقلة يساهم في هذا المجموع مرتين على الأكثر. لتكن T الكلفة؛ عندئذ 5≤2T، ولذلك T≥5/2. يطابق الحد شاهد الأنصاف، فيثبت القيمة.

التلوين الصحيح للدورة يحتاج 3. مع لونين، التناوب على A B C D E يعطي A وE اللون نفسه، فتفشل الحافة AE؛ الشاهد 12123 يختلف على الحواف الخمس. القيمة 5/2 ليست إعادة تسمية لهذا الشاهد ولا تقريب 3.

شهادة الرؤوس تمنع أي تغطية أرخص

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

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

أعد ترتيب المجموع المحدود: مساهمة كل مجموعة I هي x_I مضروبًا في مجموع y_v داخلها. هذا المجموع الداخلي لا يزيد على 1، وx_I غير سالب، فتكون المساهمة لا تزيد على x_I. إذن مجموع أوزان الرؤوس لا يزيد على مجموع أوزان المجموعات، أي لا يتجاوز الكلفة.

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

في C5، ضع y_v=1/2 عند كل رأس. كل مجموعة مستقلة تسع اثنين، فمجموع y داخلها لا يزيد على 1. مجموع أوزان الرؤوس 5/2، ويساوي كلفة تغطية الأزواج؛ لذلك لا تغطية أرخص.

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

n/alpha حد أدنى قد يكون أصغر من القيمة

التلوين الصحيح يختلف عند طرفي كل حافة، ويقلل عدد الألوان. [2] فئاته مستقلة؛ إعطاء كل فئة وزن 1 يحقق تغطية الجميع، فيعطي حدًا أعلى للتلوين الكسري.

إذا كان n عدد الرؤوس و alpha أكبر حجم مجموعة مستقلة، فإن n/alpha حد أدنى للعدد اللوني الكسري. [4] هذا حد، ولا يلزم أن يساوي القيمة.

اشتق الحد مباشرة: مجموع تغطيات الرؤوس لا يقل عن n. إذا كان كل حجم مستقل لا يتجاوز alpha، فالوزن الواحد يساهم في تغطية عدد من الرؤوس لا يتجاوز alpha. لتكن T الكلفة؛ إذن n≤alpha×T، فتكون T≥n/alpha.

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

النجمة AB AC AD لها alpha=3، ومن ثم n/alpha=4/3. لكن الحافة AB تفرض حدًا 2 بشهادة وزن 1 على A وB. مجموعة المركز ومجموعة الأوراق، بوزن 1 لكل منهما، تغطي الجميع بكلفة 2؛ القيمة 2 لا 4/3.

الماسة AB AC AD BC BD لها alpha=2، بالمجموعة CD، فيكون n/alpha=2. المثلث ABC يفرض 3، والتقسيم A ثم B ثم CD بأوزان 1 يحقق 3؛ القيمة 3 لا 2.

هذه الشواهد تمنع تعميم مساواة القيمة بـ n/alpha. كذلك لا تعني كلفة صحيحة أن المسألة صارت اختيار مجموعة واحدة لكل رأس؛ افحص قيود التغطية والحد الأدنى في الرسم نفسه.

المثلث مع حافة منفصلة يحتاج 3 لا 5

خذ المثلث ABC مع الحافة DE، بلا حواف بينهما. ثلاث مجموعات AD وBE وC وحده، بوزن 1 لكل مجموعة، تغطي الجميع بكلفة 3؛ كل مجموعة مستقلة لأنها لا تجمع رأسين من المثلث أو طرفي DE.

المثلث يفرض 3 بشهادة وزن 1 عند A وB وC، و 0 عند D وE. في أي مجموعة مستقلة رأس واحد من المثلث على الأكثر، فيصح الحد. إذن القيمة 3، وليست مجموع قيمة المثلث 3 والحافة 2.

الرسم التوضيحي يعرض تغطية أخرى بالكلفة 3: AD وBE وCD بأوزان 1. هنا D تجمع 2 من مجموعتين، وبقية الرؤوس تجمع 1؛ الزيادة مسموحة لأن القيد حد أدنى للتغطية، وليس مساواة إلزامية.

في هذا الرسم n=5 و alpha=2، لأننا نختار رأسًا من المثلث ورأسًا من الحافة. الحد n/alpha=5/2 أصغر من القيمة 3؛ ليس رسمًا ذا مساواة رغم وجود مجموعة مستقلة من حجم 2.

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

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

المثلث مع معزولين D وE يقبل AD وBE وC بأوزان 1 أيضًا، وقيمته 3. هنا alpha=3 بالمجموعة ADE، فيكون n/alpha=5/3؛ المعزولان يزيدان alpha لكنهما لا يخفضان حد المثلث.

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

C7 تعطي 7/3، والكامل يعطي عدد رؤوسه

على C7 بالحواف AB BC CD DE EF FG AG، أكبر مجموعة مستقلة حجمها 3. ثلاثية مستقلة موجودة، لكن أربعة رؤوس مستقلة ستحتاج أربعة فواصل حول الدورة، أي ثمانية رؤوس على الأقل، وهو أكثر من 7.

المجموعات ACE ACF ADF BDF BDG BEG CEG مستقلة. ضع وزن 1/3 لكل منها؛ كل رأس يظهر في ثلاث مجموعات، فتبلغ تغطيته 1، والكلفة 7/3. ضع أيضًا وزن شهادة 1/3 عند كل رأس؛ المجموعة المستقلة تسع 3، فمجموعها لا يزيد على 1. المجموع 7/3 يثبت الأقل.

الصحيح على C7 يحتاج 3: التناوب بلونين يفشل عند الإغلاق الفردي، والشاهد 1212123 يحقق ثلاثة. كما في C5، العدد الكسري ليس عدد أسماء الألوان في تعيين صحيح منفرد.

في K_n، كل مجموعة مستقلة غير فارغة رأس واحد. كل رأس يحتاج وزنًا 1 على الأقل، فيكون المجموع لا يقل عن n، وتحقق المنفردات بوزن 1 هذا الحد. المثلث قيمته 3، وK4 وK5 وK6 وK7 قيمها 4 و 5 و 6 و 7.

أي رسم ثنائي الأجزاء وفيه حافة يقبل مجموعة كل جانب بوزن 1، بكلفة 2. ضع وزن شهادة 1 على طرفي حافة و 0 على غيرهما؛ لا تجمعهما مجموعة مستقلة، فيثبت الحد 2. إن لم توجد حافة، فالجميع مجموعة مستقلة والقيمة 1.

لذلك P4 وP5 وP6 وP7 والنجمتان بثلاث وخمس أوراق وC4 وC6 وK2,3 وK3,3 قيمها 2. حافتان منفصلتان، أو حافة مع معزولين، قيمتهما 2 أيضًا؛ المعزولات تضاف إلى مجموعات التغطية المستقلة، ولا تسقط من القيد.

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

الحصر الرباعي لا يثبت أن كل قيمة عدد صحيح

ثبتنا A B C D والحواف الست الممكنة AB AC AD BC BD CD. اختيار إبقاء أو حذف كل حافة يعطي 2^6=64 رسمًا مسمى. لكل رسم، حصرنا المجموعات المستقلة غير الفارغة؛ مجموع أعدادها 481.

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

في الأربعة، القيمة 1 في الرسم الخالي، 2 في 40 رسمًا، 3 في 22، 4 في K4 وحدها؛ وهي تساوي أقل التلوين الصحيح في كل 64. هذا حصر مقيد بأربعة رؤوس، وليس مساواة عامة؛ C5 وC7 تعطيان كسورًا خارج الحصر.

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

في 23 مثالًا مسمى، راجعنا أيضًا C5 وC7 والمثلث مع حافة والمثلث مع معزولين، مع الأمثلة السابقة. بعض الشواهد تأتي من تقسيم صحيح، وبعضها من أوزان متساوية على مجموعات مستقلة قصوى؛ نجاحها لا يغني عن فحص شهادة الحد الأدنى.

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

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

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