مبرهنة هول: لماذا لا يكفي فحص كل شخص وكل زوج من الأشخاص؟

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

لأن ثلاثة أشخاص قد يشتركون في مهمتين فقط، رغم أن كل شخص وكل زوج من الأشخاص يملك خيارات كافية. في مثالنا S={A,B,C} وN(S)={1,2}؛ الشرط2≥3 يفشل. إضافة الحافة C3 تتيح المطابقة A1 وB2 وC3 وD4. الفحوص المذكورة تخص جهة الأشخاص؛ زوج المهام {3,4} يفشل أيضًا في الرسم الأصلي.

• نقسم الرؤوس إلى أشخاص L={A,B,C,D} ومهام R={1,2,3,4}. الحافة تعني أهلية الشخص للمهمة، والمطابقة الكاملة تعطي كل شخص مهمة مختلفة. في هذا المثال المتوازن، تتحقق الإمكانية إذا وفقط إذا تحقق |N(S)|≥|S| لكل مجموعة S من L. [1]
• N(S) اتحاد المهام التي يصل إليها فرد واحد على الأقل من S؛ نحسب المهمة مرة واحدة مهما تعددت حوافها. ليست قائمة بالخيارات المشتركة بين جميع أفراد المجموعة، ولا مجموع درجاتهم.
• A وB وC لكل منهم الخياران1 و2؛ ولـD الخياران3 و4. كل فرد يرى مهمتين، وكل زوج من الأشخاص يرى مهمتين أو أربعًا، والأشخاص الأربعة يرون المهام الأربع. النجاح هنا لا يغطي اختبار كل مجموعة.
• المجموعة {A,B,C} ترى {1,2} فقط؛ لا يمكن توزيع ثلاث مهام مختلفة من مهمتين. أكبر مطابقة حجمها3، مثل A1 وB2 وD3. ومن الجهة الأخرى، المهام {3,4} لا يجاورها إلا D؛ لا نعمم نجاح الأزواج على جهتي الرسم.
• نضيف خيارًا جديدًا هو C3، فيصبح ABC قادرًا على الوصول إلى ثلاث مهام. نفحص مجموعات الأشخاص الخمس عشرة غير الفارغة، ثم نقدم A1 وB2 وC3 وD4 كشاهد صريح على المطابقة الكاملة؛ لا يكفي زوال العائق القديم وحده.
• إعادة ترتيب إسناد على الحواف القديمة لا تنشئ مهمة ثالثة لـABC. نثبت هنا شروط الأهلية وعدد المهام المختلفة، بلا أوزان أو تفضيلات. الرسم المعدل مختلف بحافة واحدة، وله أيضًا المطابقة A2 وB1 وC3 وD4؛ الحل ليس وحيدًا.

ما المطلوب من الإسناد الكامل؟

لدينا أربعة أشخاص نسميهم A وB وC وD، وأربع مهام نسميها1 و2 و3 و4. نرسم الأشخاص يسارًا والمهام يمينًا، ونصل شخصًا بمهمة عندما نسمح له بأدائها. لا نصل شخصين ببعضهما ولا مهمتين ببعضهما.

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

في الرسم الثنائي المتوازن، تعطي مبرهنة هول معيارًا: توجد مطابقة كاملة إذا وفقط إذا كان |N(S)|≥|S| لكل مجموعة S من جهة الأشخاص. [1] الرمز |S| عدد الأشخاص في المجموعة، والرمز |N(S)| عدد مهامها المجاورة المختلفة.

سبب ضرورة الشرط مباشر: لو أسندنا مهمة مختلفة لكل فرد من S، لاحتجنا على الأقل |S| مهام ضمن N(S). شرحنا لهذا الاتجاه لا يثبت بمفرده أن الشرط كافٍ في كل رسم؛ الكفاية هي الجزء الذي نستند فيه إلى المبرهنة.

احسب اتحاد الخيارات لا عدد الحواف

نثبت الحواف الثماني فقط: A1 وA2 وB1 وB2 وC1 وC2 وD3 وD4. أسماء الحواف تجمع اسم الشخص ورقم المهمة؛ A1 يعني أهلية A للمهمة1. الأرقام أسماء مهام، وليست تكاليف أو درجات.

جيران المجموعة هم المهام التي يجاورها أي فرد منها. للمجموعة {A,B} أربع حواف خارجة، لكن N({A,B})={1,2} يضم مهمتين فقط. تكرر ظهور المهمة1 في A1 وB1 لا يجعلها مهمتين مستقلتين.

وفي المقابل، جيران {A,D} هم {1,2,3,4}. ليست هناك مهمة يشترك A وD في إمكان أدائها، ومع ذلك اتحاد خياراتهما يتضمن أربع مهام. إذن استخدام تقاطع الخيارات بدل الاتحاد يغير السؤال تمامًا.

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

كيف تنجح الفحوص الفردية والزوجية؟

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

الأزواج من A وB وC هي {A,B} و{A,C} و{B,C}. كل زوج منها يرى {1,2}؛ عدد الأشخاص2 وعدد المهام2، فينجح الاختبار بالمساواة. تشابه خيارات الشخصين لا يمنع إسنادهما وحدهما.

الأزواج التي يدخل فيها D هي {A,D} و{B,D} و{C,D}. كل زوج منها يرى المهام الأربع، فينجح أيضًا. بذلك فحصنا أزواج الأشخاص الستة كلها، لا مجرد زوج مناسب للمثال.

أما المجموعة L كلها، فجيرانها R كلها: أربعة أشخاص وأربع مهام. هذا الفحص يجمع الخيارات على مستوى الرسم كله، لكنه يخفي أن الشخص D وحده يملك الخيارين3 و4، فلا يستطيع أن يفتح هذين الخيارين لـA وB وC.

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

المجموعة الثلاثية تكشف استحالة الإسناد

خذ S={A,B,C}. كل حواف أفرادها تنتهي في1 أو2، ولذلك N(S)={1,2}. نحتاج ثلاث مهام مختلفة لثلاثة أشخاص، لكن المتاح مهمتان فقط. هذه الاستحالة لا تعتمد على الشخص الذي نبدأ به.

لو اخترنا A1 وB2، فلن يجد C مهمة أخرى مسموحة. ولو قدمنا C في ترتيب الاختيار، سيبقى أحد الشخصين الآخرين بلا مهمة. هذا مثال على نقص فعلي في الخيارات، لا مجرد قرار أول سيئ يمكن إصلاحه بتبديل الأسماء.

يمكن إسناد ثلاث مهام: A1 وB2 وD3 حواف ذات أطراف مختلفة. ولا يمكن إسناد أربع، لأن ذلك يستلزم إسناد A وB وC جميعًا إلى ثلاث مهام من المجموعة ذات المهمتين. إذن أكبر حجم مطابقة هنا3.

ومن جهة المهام، المجموعة {3,4} لا يجاورها إلا D، فلا يستطيع شخص واحد تنفيذ مهمتين مختلفتين في الإسناد الذي عرفناه. يشرح ذلك العائق نفسه من جهة أخرى. قولنا إن كل زوج ينجح مقيد بأزواج الأشخاص؛ أزواج المهام لا تنجح كلها.

المجموعات الثلاثية التي يدخل فيها D ترى المهام الأربع؛ فكل منها يحتوي شخصين من ABC ومعهما D. لذلك لا يوجد عائق آخر على جهة الأشخاص. المجموعة الخالية عددها0 وجيرانها خالون أيضًا، فلا تضيف اختبارًا صعبًا.

أضف C3 ثم قدم إسنادًا صالحًا

نغير الأهلية بإضافة الحافة C3 فقط، مع إبقاء الحواف الثماني القديمة. يصبح C قادرًا على المهمة3 إلى جانب1 و2. الآن N({A,B,C})={1,2,3}، فينجح اختبار المجموعة الثلاثية الذي فشل سابقًا.

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

مع ذلك نعرض شاهدًا واضحًا: M={A1,B2,C3,D4}. كل حافة مسموحة في الرسم المعدل، وكل شخص يظهر مرة، وكل مهمة تظهر مرة. هذه الحواف الأربع تحقق المطلوب مباشرة، فلا يقتصر الدليل على عبارة أن الاختبار نجح.

ومن جهة المهام، صارت3 مجاورة لـC وD، وبقيت4 مجاورة لـD. الزوج {3,4} أصبح يملك شخصين مختلفين، ويمكن إسناد3 إلى C و4 إلى D. فحص المجموعات الخمس عشرة في هذه الجهة ينجح أيضًا.

اللوحة اليمنى من الصورة الداخلية تميز C3 والحواف المختارة. ولنا خيار آخر هو A2 وB1 وC3 وD4؛ تبديل المهمتين1 و2 بين A وB يحافظ على الصحة. لا ندعي أن المطابقة الكاملة وحيدة.

ما الذي ينبغي فحصه قبل الحكم؟

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

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

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

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

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