المطابقة الكاملة تختار حواف لا تتشارك في رأس، بحيث يدخل كل رأس في حافة واحدة منها. لذلك يلزم عدد زوجي من الرؤوس. [2] لكن العدد الزوجي والاتصال لا يكفيان: سنبني رسمًا من عشرة رؤوس، ثم نحذف رأسًا واحدًا لنكشف ثلاثة مكونات ذات أعداد فردية من الرؤوس.
الخلاصة السريعة
لأن كل مكون فردي بعد حذف V يحتاج حافة مطابقة تصل أحد رؤوسه بـV. لدينا ثلاثة مثلثات، لكن V لا يدخل إلا في حافة مطابقة واحدة؛ تبقى رؤوس بلا شريك. نختار S={V} فنجد o(G-S)=3>|S|=1. إضافة CF بين مثلثين تتيح المطابقة M={AB,DE,CF,GV,HI}.
- نثبت ثلاثة مثلثات ABC وDEF وGHI، ونصل V بالرؤوس A وD وG. الرسم فيه10 رؤوس و12 حافة، وهو متصل وأقل درجة فيه2، لكنه ليس ثنائيًا؛ كل مثلث يمنع تقسيمًا تعبر فيه كل حافة بين جهتين.
- المكون الفردي هو مكون متصل عدد رؤوسه فردي، لا مكون حوافه أو درجاته فردية. حذف مجموعة S يعني حذف رؤوسها وحوافها المتصلة بها، ثم حساب المكونات في G-S.
- تعطي مبرهنة توت معيارًا للرسم العام: توجد مطابقة كاملة إذا وفقط إذا كان o(G-S)≤|S| لكل مجموعة رؤوس S، حيث o عدد المكونات الفردية بعد الحذف. [1] في مثالنا S={V} يترك ثلاثة مكونات فردية مقابل رأس محذوف واحد.
- كل مثلث يحتاج شريكًا خارج المثلث لتغطية رؤوسه الثلاثة بالمطابقة. الطريق الخارجي الوحيد يمر عبر V، ولا يستطيع V خدمة المثلثات الثلاثة معًا. المطابقة AB وDE وGV وHI تغطي8 رؤوس؛ أكبر حجم مطابقة في الأصل4، لا5.
- نضيف CF فنصل مثلثي ABC وDEF. بعد حذف V صار المكون الأول6 رؤوس والمكون الثاني3، فعدد المكونات الفردية1. ونقدم AB وDE وCF وGV وHI كشاهد من خمس حواف يغطي الرؤوس العشرة، مع فحص جميع مجموعات الحذف.
- اجتياز الحواف في ممر، وتغطية كل رأس بحافة مطابقة واحدة، سؤالان مختلفان. لا نعد أطوال الخطوط أو نغير الأهلية بمجرد إعادة ترتيب الاختيار. الحافة CF جديدة، والرسم المعدل يختلف عن الأصلي.
عشرة رؤوس متصلة، لكن هل يمكن إقرانها؟
نسمي الرؤوس A وB وC وD وE وF وG وH وI وV. الحواف داخل المثلثات هي AB وBC وAC، ثم DE وEF وDF، ثم GH وHI وGI. نضيف AV وDV وGV فقط لربط المثلثات بالرأس V.
كل رأس يصل إلى بقية الرسم عبر هذه الحواف، ولذلك الرسم متصل. درجات A وD وG وV تساوي3، ودرجات الرؤوس الستة الباقية تساوي2. لا يوجد رأس معزول أو ورقة ذات حافة واحدة؛ مجموع الدرجات24، أي طرفان لكل واحدة من12 حافة.
المطابقة الكاملة تحتاج أن يقع كل رأس في حافة مختارة واحدة بالضبط. [2] في رسمنا ذي الرؤوس العشرة يعني ذلك خمس حواف ذات عشرة أطراف مختلفة. اختيار خمس حواف كيفما اتفق لا يكفي؛ تكرر رأس منها يترك رأسًا آخر دون تغطية.
الحروف أسماء رؤوس، والحواف غير موجهة. AV وVA اسمان للاتصال نفسه، لا خياران مستقلان. الرسم بلا حلقات ذاتية وحواف مكررة، وأطوال الخطوط وتقاطعاتها ليست بيانات إضافية.
ما الذي نحذفه وما الذي نعده؟
خذ S={V}. نزيل V ونزيل الحواف AV وDV وGV المتصلة به. لا نزيل A أوD أوG؛ تبقى هذه الرؤوس داخل مثلثاتها. الحذف خطوة لتحليل الرسم، وليس طلبًا للعثور على مطابقة تغطي تسعة رؤوس بدل عشرة.
الرسم الباقي G-S يتكون من ABC وDEF وGHI، بلا حافة بين مثلثين. كل واحد متصل وعدد رؤوسه3، ولذلك لدينا ثلاثة مكونات فردية. المقصود بفردية المكون هو عدد رؤوسه؛ داخل المثلث درجة كل رأس2 وهي زوجية.
نكتب o(G-S) لعدد المكونات الفردية، لا لعدد المكونات كلها ولا لعدد الرؤوس الفردية الدرجة. هنا القيمتان الأولى والثانية تتساويان3 لأن المكونات الثلاثة فردية؛ لاحقًا سيظهر مكون زوجي لا يدخل في o.
في اللوحة اليمنى من الصورة الرئيسية حذفنا V فعلًا، ولون كل مثلث يحدد مكونًا من ثلاثة رؤوس. تقاطع خطوط الرسم الأصلي على الصفحة لا يصنع وصلات بين المثلثات؛ الدوائر المسماة وحدها رؤوس.
شرط توت يفحص كل مجموعة حذف
تقرر مبرهنة توت أن الرسم يملك مطابقة كاملة إذا وفقط إذا كان o(G-S)≤|S| لكل مجموعة من رؤوسه. [1] نسمح بالمجموعة الخالية أيضًا، ولا نقصر S على جهة مفترضة من جهتين.
عند S={V} في مثالنا، عدد الرؤوس المحذوفة1، وعدد المكونات الفردية3. الشرط3≤1 غير صحيح، فتمنع هذه المجموعة وحدها وجود المطابقة الكاملة. لا يلزم إيجاد مخالفات كثيرة أو تجربة كل ترتيب لاختيار الحواف حتى نثبت الفشل.
أما عند S=∅، فالرسم الأصلي متصل وفيه10 رؤوس؛ المكون الوحيد زوجي، ومن ثم o(G)=0. النجاح0≤0 يبين أن فحص المجموعة الخالية لا يحسم المسألة، رغم أنه يفحص عدد رؤوس المكونات في الرسم كله.
إذا حذفنا V وA، بقي BC مكونًا ذا رأسين، وبقي مثلثا DEF وGHI فرديين. صار o(G-S)=2 وعدد المحذوفين2، فينجح هذا الاختبار بالمساواة. تغيير S يغير المكونات التي نعدها.
يعرض الجدول حالات قبل إضافة الحافة الجديدة وبعدها. يكفي اختبار فاشل واحد لنفي المطابقة الكاملة، لكن نجاح اختبار واحد لا يثبت المعيار الذي يطلب جميع المجموعات.
| الحالة ومجموعة الحذف | أعداد رؤوس المكونات | اختبار الفردية |
|---|---|---|
| الأصل S=∅ | 10 | 0≤0 ينجح |
| الأصل S={V} | (3,3,3) | 3≤1 يفشل |
| الأصل S={V,A} | (2,3,3) | 2≤2 ينجح |
| بعد CF، S={V} | (6,3) | 1≤1 ينجح |
| حذف كل الرؤوس | لا مكونات | 0≤10 ينجح |
لماذا تحتاج المكونات الفردية رؤوسًا مختلفة خارجها؟
افترض وجود مطابقة كاملة في الرسم الأصلي. داخل مثلث من ثلاثة رؤوس، كل حافة مطابقة داخلية تغطي رأسين. لا يمكن تغطية العدد الفردي كله بأزواج داخل المثلث؛ لا بد أن تدخل حافة مختارة تخرج منه.
الاتصال الخارجي الوحيد لمثلث ABC هو AV، ولـDEF هو DV، ولـGHI هو GV. ستحتاج المثلثات الثلاثة إلى هذه الحواف الثلاث في المطابقة الكاملة. لكنها تتلاقى كلها في V، والمطابقة تمنع استعمال الرأس نفسه أكثر من مرة.
السبب نفسه يفسر ضرورة الشرط عمومًا: كل مكون فردي من G-S يحتاج حافة مطابقة إلى S، لأن لا حواف بين مكونات G-S. والمكونات المختلفة تحتاج رؤوسًا مختلفة من S؛ لا يستطيع رأس محذوف واحد أن يشارك في حافتي مطابقة.
في المثال، نستطيع اختيار AB وDE وGV وHI. أطراف الحواف الثمانية مختلفة، ويبقى C وF دون شريك. هذا اختيار صالح من أربع حواف. وجود مطابقة من خمس كان سيغطي الرؤوس العشرة، وقد أثبتنا استحالته؛ إذن أكبر حجم هو4.
برهان الضرورة يشرح العائق، لكنه لا يثبت وحده كفاية الشرط في جميع الرسوم. نستند إلى مبرهنة توت في الكفاية؛ لا نحول نجاح مثال أو حصر مجموعاته إلى برهان عام لكل عدد من الرؤوس.
حافة CF تصل مكونين وتسمح بخمس حواف
نضيف CF فقط إلى الحواف الاثنتي عشرة الأصلية. عند حذف V هذه المرة، يتصل ABC وDEF عبر CF، فيصبحان مكونًا واحدًا من6 رؤوس. ويبقى GHI مكونًا مستقلًا من3 رؤوس.
إذن عدد المكونات الكلي2، لكن عدد المكونات الفردية1 فقط. المكون ذو الرؤوس الستة لا يدخل في o(G-S). بالنسبة إلى S={V} أصبح الاختبار1≤1 ناجحًا؛ لا نخلط نجاحه وحده بنجاح كل المجموعات.
نقدم المطابقة M={AB,DE,CF,GV,HI}. AB تغطي A وB، وDE تغطي D وE، وCF تغطي C وF، وGV تغطي G وV، وHI تغطي H وI. ظهرت أسماء الرؤوس العشرة مرة واحدة، وكل حافة موجودة في الرسم المعدل.
هذا الشاهد يثبت وجود مطابقة كاملة مباشرة. وفي فحص المثال حسبنا المكونات لكل مجموعة حذف من الرؤوس العشرة، بما فيها الخالية والمجموعة الكاملة؛ جميع الاختبارات1024 نجحت بعد الإضافة. الفحص يخص هذين الرسمين المحددين.
الذهب في اللوحة اليمنى من الصورة الداخلية يحدد الحواف الخمس. CF لم تكن موجودة في الأصل؛ ليست نتيجة لتبديل ترتيب الحواف القديمة. نصل بين مكونين فرديين كي يستطيع رأس من الأول الاقتران برأس من الثاني.
افصل فردية المكون من فردية الدرجة
درجات رؤوس المثلث بعد حذف V تساوي2، لكن المثلث يضم3 رؤوس. لهذا يكون مكونًا فرديًا رغم زوجية درجاته. لا تستبدل عدد الرؤوس في كل مكون بعد الحذف بعدد الرؤوس الفردية الدرجة في الرسم الأصلي.
المطابقة تختار حواف ذات أطراف منفصلة؛ لا تطلب اجتياز كل حافة ولا تسمح بتغطية الرأس مرة ثانية بحافة أخرى. شرط ممر يستخدم الحواف مرة واحدة يعالج مسألة مختلفة، فلا نستنتج المطابقة الكاملة من اختبار درجات خاص بالممرات.
كذلك لا نفرض تقسيمًا إلى أشخاص ومهام على مثالنا. مثلث ABC لا يقبل تقسيمًا تعبر فيه حوافه الثلاث بين جهتين: فصل A عن B وفصل B عن C يجعلان A وC في الجهة نفسها مع وجود AC.
حذف V فحص يكشف اعتماد ثلاثة مكونات فردية على رأس واحد. أما إضافة CF فتعيد تشكيل الرسم وتسمح بمطابقة كاملة. عند قراءة الشرط سجل المجموعة المحذوفة والمكونات الباقية وعدد رؤوس كل منها، ثم قارن عدد الفردية بعدد المحذوفين.
رسمنا الأصلي يجمع عددًا زوجيًا واتصالًا وغياب الرؤوس ذات الخيار الوحيد، ومع ذلك يفشل. والرسم المعدل يقدم شاهدًا صريحًا من خمس حواف. هذه المقارنة توضح سبب البحث عن عائق المكونات، لا الاكتفاء بالعدد الكلي أو اتصال الرسم.
اقرأ أيضًا: استرجاع الرسوم البيانية: نوع العلاقة واتجاهها
اقرأ أيضًا: أنواع الرسم البياني: اختر الشكل الذي يجيب عن السؤال
المراجع
أُعدّ هذا المقال بمساعدة الذكاء الاصطناعي، وخضع لمراجعة ذاتية بالأداة نفسها. لا يُنسب إلى مراجع بشري أو خبير مستقل. منهجية المحتوى.