المطابقة الكسرية: كيف يتجاوز المثلث حافة واحدة؟

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

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

• في المطابقة الكسرية نعين لكل حافة قيمة غير سالبة، ويجب ألا يتجاوز مجموع القيم المتصلة بكل رأس 1. نكبر مجموع قيم الحواف؛ المطابقة الصحيحة تقصرها على 0 أو 1. [1] نفترض رسمًا محدودًا وبسيطًا وغير موجه وبلا حلقات أو أوزان هدف مختلفة؛ لكل رأس سعة 1.
• في المثلث A B C وحوافه AB AC BC، الاختيار الصحيح AB وحده حجمه 1. القيم(1/2,1/2,1/2) تجعل أحمال A وB وC كلها 1، والحجم 3/2؛ لا تصبح مجموعة الحواف الثلاث مطابقة صحيحة.
• جمع قيود الرؤوس يحسب كل حافة مرتين، فيعطي 2×المجموع≤n. النصف لكل حافة يبلغ حد 3/2 في المثلث وحد 5/2 في الدورة C5، مقابل أكبر حجم صحيح 1 و 2. مساواة القيود تفرض الأنصاف وحدها في المثلث وC5.
• النقطة القصوى لا تكون خليطًا داخليًا من نقطتين ممكنتين مختلفتين؛ في مجموعة قيود خطية ممكنة ومحدودة يتحقق أفضل هدف خطي عند واحدة منها. [2] في دورة C4، الحلان AB CD وAD BC حجمهما 2؛ متوسطهما يعطي نصفًا لكل حافة بالحجم 2 نفسه، فيثبت أن هذه النقطة ليست قصوى، رغم أمثليتها. الأنصاف قصوى في المثلث وC5، وغير قصوى في C4.
• أضف الورقة D بحافة AD إلى المثلث. إعطاء نصف للحواف الأربع يرفع حمل A إلى 3/2، فيفشل الشرط. الحل الأمثل الصحيح والكسري الوحيد هو AD BC بالحجم 2؛ مساواة الأحمال تجبر AD=1 ثم AB=AC=0 وBC=1.
• راجعنا 64 قائمة حواف على أربعة أسماء:2972 نظام قيود فعالة مرشحًا، و 336 نقطة قصوى مختلفة داخل مدخلاتها. قارناها بـ4096 تعيين على الشبكة 0 و 1/2 و 1، منها 972 ممكنة؛ اتفقت أفضل قيم الطريقتين الكسريتين، ثم قورنت بأحجام المطابقات الصحيحة. حللنا أنظمة مستقلة بكسور دقيقة، وتحققنا من كل القيود بعد الحل.
• وجدنا فرقًا بين الصحيح والكسري في 4 مدخلات فقط: مثلث مع رأس معزول بكل اختيار لاسمه. نقاط الفحص القصوى كانت بإحداثيات 0 و 1/2 و 1؛ هذا نتيجة للنطاق المحدود، ولا نقدم منه مبرهنة عامة لكل أحجام الرسوم أو خوارزمية سريعة.

المتغير للحافة، والقيد عند الرأس

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

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

في الاختيار الصحيح،1 تعني أننا اخترنا الحافة كاملة، و 0 تعني تركها. شرط الرأس يمنع حافتين مختارتين من المشاركة فيه. عند السماح بالكسر، يمكن أن تكون حافتان لهما القيمة 1/2 متصلتين بالرأس نفسه، لأن مجموعهما 1.

القيمة x_AB تخص الحافة AB نفسها من طرفيها؛ لا نجعلها نصفًا عند A وقيمة أخرى عند B. وهي تظهر في قيد A وقيد B، لكنها تدخل هدف مجموع الحواف مرة واحدة فقط.

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

المثلث يقبل ثلاثة أنصاف، لا حافتين كاملتين

أسماء الأصل A وB وC، وحوافه الثلاث فقط AB وAC وBC. أي حافتين تشتركان في رأس، لذا أكبر مطابقة صحيحة حافة واحدة. يمكن اختيار AB، أو AC، أو BC، لكن لا نختار اثنتين منها معًا.

نكتب القيم بالترتيب AB AC BC. اختيار AB وحدها هو(1,0,0)، وأحمال A B C هي 1 و 1 و 0. الحجم 1 يحسب قيمة الحافة المختارة، ولا يعد الرأس الحر وكأنه نصف حافة.

أما(1/2,1/2,1/2)، فتعطي عند A مجموع AB وAC وهو 1، وعند B مجموع AB وBC وهو 1، وعند C مجموع AC وBC وهو 1. كل قيد محترم، والحجم 1/2+1/2+1/2=3/2.

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

الجدول يراجع قيم الحواف بدل عد الخطوط الملونة. كل واحدة من الثلاث موجبة في الحل الكسري، لكن حجم هذا الحل هو مجموع القيم 3/2، لا عدد الحواف الموجبة 3 ولا عدد الأزواج الكاملة 2.

جمع قيود الرؤوس يثبت أن 3/2 هي الأكبر

قيود المثلث هي x_AB+x_AC≤1، وx_AB+x_BC≤1، وx_AC+x_BC≤1. عند جمعها تظهر قيمة كل حافة مرتين، فنحصل على 2(x_AB+x_AC+x_BC)≤3.

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

والحل الكسري الأمثل وحيد في المثلث. إذا بلغ المجموع 3/2، صار مجموع أحمال الرؤوس 3، وكل حمل لا يزيد على 1؛ فلا بد أن تكون الأحمال الثلاثة 1. طرح معادلتي A وB يعطي x_AC=x_BC، وبالمثل تتساوى القيم الثلاث، فتكون كل منها 1/2.

الحجة نفسها تعطي في أي رسم ضمن النموذج المعلن 2×المجموع≤n، لأن كل حافة لها طرفان مختلفان. هذا حد عام، لا وعد بأن كل رسم يحققه؛ الرأس المعزول مثلًا لا يحمل أي قيمة موجبة.

خذ الدورة الخماسية A-B-C-D-E-A، وحوافها AB وBC وCD وDE وAE. النصف على كل حافة يجعل كل حمل 1 ويحقق الحجم 5/2. المطابقة الصحيحة AB CD من حافتين تبلغ الأكبر الصحيح؛ ثلاث حواف مستقلة كانت ستحتاج ستة رؤوس.

لأن 5/2 يحقق حد n/2، فهو الأكبر الكسري في هذه الدورة. وتشدد جميع قيود الرؤوس يفرض التناوب x و 1−x حول الدورة؛ عند الرجوع بعد عدد فردي من الحواف نحتاج x=1−x، فتكون القيم أنصافًا. هذه حجة للدورة المحددة، لا تحويل 5/2 إلى عدد حواف صحيحة.

حل أمثل قد يقع بين حلين آخرين

النقطة القصوى لا تكون خليطًا داخليًا من نقطتين ممكنتين مختلفتين؛ في مجموعة قيود خطية ممكنة ومحدودة يتحقق أفضل هدف خطي عند واحدة منها. [2]

نأخذ الدورة A-B-C-D-A، بحواف AB وAD وBC وCD فقط. يوجد حلان صحيحان كاملان: AB CD، أو AD BC. في ترتيب الحواف AB AD BC CD، متجهاهما(1,0,0,1) و(0,1,1,0).

متوسط المتجهين هو(1/2,1/2,1/2,1/2). عند كل رأس حافتان بنصفين، فالحمل 1؛ ومجموع الحواف 2. الحد n/2=2 يثبت أن هذا حل كسري أمثل أيضًا، مثل الحلين الصحيحين.

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

النقطة هنا متجه قيم الحواف، وليست أحد الرؤوس المسماة A أوB أوC أوD في الرسم. لدينا أربعة أعداد تتغير مع الاختيار، ومجموعة الحلول تعيش في مساحة هذه الأعداد؛ صورة الدورة تساعد على قراءة القيود، لا على رسم تلك المساحة كاملة.

وفي المثلث، كانت الأنصاف أمثلًا وحيدًا، فلا يمكن أن تكون خليطًا داخليًا من حلين مختلفين ممكنين: لو كانا يعطيان المتوسط الأمثل، فلا يمكن أن يتجاوز هدفهما 3/2، ويجبر متوسط الهدفين أن يساوياه كليهما، فيخالف الوحدانية. يختلف الحكم بالقصوى رغم تشابه عبارة «نصف على كل حافة».

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

النصف لكل حافة قد يخرق السعة بعد إضافة ورقة

نعود إلى مثلث A B C، ونضيف D والحافة AD فقط. قائمة الحواف AB وAC وAD وBC. صار عند A ثلاث حواف؛ إعطاء نصف لكل واحدة يجعل حمله 3/2، فيتجاوز 1 ويمنع هذا التعيين.

فحص سعة A يكفي لرفض الأنصاف، حتى لو بقي حمل B وC مساويًا 1 وحمل D مساويًا 1/2. لا نأخذ قاعدة النصف من مثال ذي درجة 2 ونطبقها على رأس ذي درجة 3 دون جمع قيمه.

الحافتان AD وBC لا تتشاركان رأسًا وتغطيان الأربعة، فتقدمان اختيارًا صحيحًا بحجم 2، وهو ممكن كسريًا أيضًا. وحد n/2=2 يمنع أي حل كسري أكبر، فتتساوى هنا القيمة الصحيحة والقيمة الكسرية.

هذا التعيين الأمثل وحيد. بلوغ الحجم 2 يجعل مجموع الأحمال 4، فتكون كل منها 1. قيد D عند المساواة يعطي x_AD=1. عند A لا يبقى شيء للحافتين AB وAC، وعدم السلبية يجبرهما 0؛ ثم يجبر قيد B أوC قيمة BC على 1.

في ترتيب AB AC AD BC، الحل هو(0,0,1,1). إضافة الورقة غيرت القيود والنتيجة: اختفى فرق 3/2 مقابل 1، وفشل التعيين الذي كان أمثلًا في المثلث. لا نفسر ذلك بأنه حذف كسور من الحل القديم فقط؛ الرسم نفسه تغير.

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

حصر القيود الفعالة يراجع القيمة الكسرية بدقة

في m متغيرات، تحدد m قيود فعالة مستقلة حلًا أساسيًا؛ يكون ممكنًا عندما يحقق جميع القيود. [2]

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

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

على أربعة أسماء قديمة توجد ستة أزواج محتملة للحواف، فراجعنا 2^6=64 قائمة. عبر هذه المدخلات، بلغ عدد أنظمة الحدود المرشحة 2972، وعدد النقاط القصوى بعد إزالة التكرار داخل كل مدخل 336. هذه أعداد مجمعة، لا 336 نقطة للمثلث وحده.

وقارنّا القيم المثلى بنهج مستقل يفحص كل تعيين من 0 و 1/2 و 1 للحواف الموجودة. بلغ مجموع مرشحات هذه الشبكة 4096، منها 972 تحقق القيود. اتفقت أفضل قيم الشبكة مع أفضل قيم حصر النقاط القصوى في كل مدخل؛ لم نفترض مسبقًا أن هذه الشبكة تكفي لجميع الرسوم.

حصرنا كذلك المطابقات الصحيحة باختيار رأس حر وتركه أو إقرانه بجار حر. ظهر فرق القيمة الصحيحة والكسرية في 4 مدخلات من 64: مثلث ورأس معزول، مع أربعة اختيارات لاسم المعزول. قيمها 1 و 3/2، بينما كان الفرق صفرًا في بقية المدخلات الرباعية.

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

افصل قيمة الاختيار من عدد الحواف الكاملة

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

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

لا نستعمل أوزان هدف مختلفة أو سعات أكبر من 1 أو حلقات عند الرأس أو حواف موجهة. هذه تغير المسألة التي كتبنا قيودها. كما لا نعتمد نتائج أداء خوارزمية أو ادعاء أن فحص كل أنظمة الحدود مناسب لرسم كبير.

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

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

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