التطابق في الرسوم البيانية ثنائية الأجزاء

\Does هل يحتوي الرسم البياني (graph) أدناه على تطابق (matching)؟ فإن كان كذلك، فأوجد واحدًا.

وليست كلُّ الرسوم البيانية ثنائية الأجزاء لها تطابقات. ارسم أكبر عددٍ من الأمثلة المختلفة جوهريًّا للرسوم البيانية ثنائية الأجزاء التي لا تملك تطابقات. والهدف أن تجد جميع الموانع الممكنة لوجود تطابقٍ تامّ (perfect matching) في رسمٍ بياني. اكتب الشروطَ اللازمة (necessary) لوجود تطابق في رسمٍ بياني (أي: املأ الفراغ: إذا كان في رسمٍ بياني تطابق، فإنّ ). ثمّ اسأل نفسك: هل هذه الشروط كافية (sufficient)؟ (هل صحيح أنّه إذا فإنّ في الرسم تطابق؟).

ونختم بمثالٍ آخر على مسألةٍ في نظرية الرسوم البيانية (graph theory) لتوضيح تنوّع هذا الموضوع واتّساعه.

لنفترض أنّ لديك رسمًا بيانيًا ثنائيّ الأجزاء $G\text{.}$ سيتألّف هذا من مجموعتين من الرؤوس $A$ و$B$، مع بعض الحوافّ التي تصل بعض رؤوس $A$ ببعض رؤوس $B$ (لكنّ بالطبع لا توجد حوافّ بين رأسين كلاهما في $A$ أو كلاهما في $B$). وتطابقُ $A$ هو مجموعةٌ جزئية من الحوافّ بحيث إنّ كلَّ رأسٍ في $A$ ينتمي إلى حافةٍ واحدةٍ بالضبط من المجموعة الجزئية، ولا ينتمي أيُّ رأسٍ في $B$ إلى أكثر من حافةٍ واحدة في المجموعة الجزئية. وفي التطبيق سنفترض أنّ $|A| = |B|$ (أي أنّ للمجموعتين العدد نفسه من الرؤوس)، وهذا يعني أنّ كلَّ رأسٍ في الرسم ينتمي إلى حافةٍ واحدةٍ بالضبط في التطابق. 11 وما نسمّيه تطابقًا يسمّيه أحيانًا آخر تطابقًا تامًّا أو كاملًا (complete matching). وذلك لأنّه من المثير للاهتمام النظر في التطابقات غير التامّة أيضًا. وسنسمّي تلك تطابقاتٍ جزئية (partial matching).

وقد يساعدك بعضُ السياق في فهم هذا الأمر بسهولة. تخيَّل أنّ الرؤوس في $A$ تمثّل طلبةً في صفٍّ، وأنّ الرؤوس في $B$ تمثّل مواضيعَ عروضٍ تقديمية. ونضع حافةً من رأس $a \in A$ إلى رأس $b \in B$ إذا أراد الطالب $a$ أن يقدّم عرضًا عن الموضوع $b\text{.}$ وبالطبع يريد بعضُ الطلبة تقديمَ أكثر من موضوع، لذا يكون رأسُه ذا درجةٍ أكبر من 1. وأنت المعلّم، تريد أن تُسند إلى كلّ طالبٍ موضوعَه الفريدَ الخاصّ به. ومن ثمّ تريد إيجادَ تطابقٍ لـ $A\text{:}$ تختار مجموعةً جزئيةً من الحوافّ بحيث يُطابَق كلُّ طالبٍ مع موضوعٍ واحدٍ بالضبط، ولا يُطابَق موضوعٌ مع طالبَين. 12 وكان المثالُ المعياريّ للتطابقات هو مسألةَ الزواج (marriage problem) التي كانت فيها $A$ تمثّل رجالَ البلدة، و$B$ نساءَها، وتمثّل الحافةُ زواجًا مقبولًا للطرفين. وكان التطابقُ يمثّل طريقةً لمشايخ البلدة أن يزوجوا كلَّ أهل البلدة، من غير أن يُسمح بتعدّد الزوجات. وقد اخترنا سياقًا أكثر حداثةً تبعًا للاعتبارات السياسية.

السؤال هو: متى يحتوي رسمٌ بيانيّ ثنائيّ الأجزاء على تطابقٍ لـ $A\text{?}$ ولنبدأ بالإجابة عن هذا السؤال، فكّر فيما قد يمنع الرسمَ من احتواء تطابق. وهذا لن يخبرنا بالضرورة بشرطٍ في الحالة التي يحتوي فيها الرسمُ فعلًا على تطابق، لكنّه على الأقلّ بداية.

إحدى الطرق التي قد لا يملك على أساسها $G$ تطابقًا هي أن يوجد رأسٌ في $A$ غير مجاورٍ لأيّ رأسٍ في $B$ (أي أنّ درجته 0). وماذا غير ذلك؟ وماذا لو أحبّ طالبان الموضوعَ نفسه ولا يحبّان سواه؟ فإنّ بعد إسناد ذلك الموضوع الواحد إلى الطالب الأول لا يبقى للطالب الثاني ما يحبّه، فيصبح الأمر كما لو أنّ الطالب الثاني درجته 0. أو ماذا لو أحبّ ثلاثةُ طلبةٍ موضوعَين اثنين فقط بينهم؟ وبدوره، بعد إسناد موضوعٍ إلى طالبٍ واحد، نرجع إلى الحالة السابقة وهي حالة طالبَين يحبّان موضوعًا واحدًا فقط. ويمكننا المتابعة على هذا المنوال مع طلبةٍ أكثر فأكثر.

وينبغي أن يكون واضحًا في هذه المرحلة أنّه إذا كانت هناك مجموعةٌ من $n$ طالبًا يحبّون كمجموعةٍ $n-1$ موضوعًا أو أقلّ، فإنّ التطابقَ مستحيل. وهذا صحيحٌ لأيّ قيمةٍ لـ $n\text{,}$ وأيّ مجموعةٍ من $n$ طالبًا.

ولجعل هذا الكلام أقرب إلى لغة الرسوم البيانية، لنفترض أنّ لديك مجموعةَ رؤوسٍ $S \subseteq A$. عرّف $N(S)$ على أنّها مجموعةُ كلّ الجيران (neighbors) لرؤوس $S\text{.}$ أي أنّ $N(S)$ تحوي كلَّ الرؤوس (في $B$) المجاورة لرأسٍ واحدٍ على الأقلّ من رؤوس $S\text{.}$ (وفي رسم الطلبة/المواضيع، تكون $N(S)$ مجموعةَ المواضيع التي يحبّها طلبةُ $S\text{.}$) ويمكن تلخيصُ مناقشتنا أعلاه كالتالي:

شرط التطابق.

إذا كان رسمٌ بيانيّ ثنائيّ الأجزاء $G = \{A, B\}$ يملك تطابقًا لـ $A\text{,}$ فإنّ $$\begin{equation*} |N(S)| \ge |S| \end{equation*}$$ لكلّ $S \subseteq A\text{.}$

هل العكس صحيح؟ لنفترض أنّ $G$ يحقّق شرطَ التطابق (matching condition) $|N(S)| \ge |S|$ لكلّ $S \subseteq A$ (أي أنّ لكلّ مجموعةٍ من الرؤوس جيرانٌ بعددٍ لا يقلّ عن عدد رؤوسها). هل يعني ذلك أنّ هناك تطابقًا؟ والمفاجأة أنّ نعم. الشرطُ الضروريُّ الواضحُ هو أيضًا كافٍ. 13 وهذا يحدث كثيرًا في نظرية الرسوم البيانية. فإذا تجنّبتَ الأمثلةَ المضادّةَ الواضحة، فغالبًا ما تحصل على ما تريد. وهذه مبرهنةٌ أثبتَها فيليب هول (Philip Hall) أوّلًا سنة 1935. 14 وهناك أيضًا صيغةٌ لانهائية من هذه المبرهنة، أثبتَها مارشال هول (Marshal Hall) الابن. لكنّ التسمية مصادفة، إذ لا تربط بين الهولين صلةُ قرابة.

مبرهنة 2.7.1. مبرهنة زواج هول.

ليكن $G$ رسمًا بيانيًا ثنائيّ الأجزاء ذا المجموعتين $A$ و$B\text{.}$ عندئذٍ يملك $G$ تطابقًا لـ $A$ إذا وإذا فقط $$\begin{equation*} |N(S)| \ge |S| \end{equation*}$$ لكلّ $S \subseteq A\text{.}$

وهناك عددٌ كبيرٌ جدًّا من البراهين المختلفة لهذه المبرهنة، ويكفي بحثٌ سريع على الإنترنت كي تبدأ.

وإلى جانب تطبيقها في الزواج ومواضيع عروض الطلبة، فإنّ للتطابقات تطبيقاتٍ في كلّ مكان. ونختم بمثالٍ من هذا النوع.

المثال 2.7.2.

لنفترض أنّك توزّع 52 بطاقةَ لعبٍ عادية على 13 مجموعة، كلّ مجموعةٍ منها 4 بطاقات. اثبت أنّ بإمكانك دائمًا أن تختار بطاقةً واحدةً من كلّ مجموعة فتحصل على واحدةٍ من كلٍّ من قيم البطاقات الثلاث عشرة: آس، 2، 3، …، 10، جاك، ملكة، وملك.

الحلّ. إنّ فعل ذلك مباشرةً سيكون صعبًا، لكنّنا يمكننا الاستعانة بشرط التطابق. أنشئ رسمًا بيانيًا $G$ فيه 13 رأسًا في المجموعة $A\text{,}$ يمثّل كلٌّ منها إحدى قيم البطاقات الثلاث عشرة، و13 رأسًا في المجموعة $B\text{,}$ يمثّل كلٌّ منها إحدى المجموعات الثلاث عشرة. ارسم حافةً بين رأس $a \in A$ ورأس $b \in B$ إذا كانت هناك بطاقةٌ قيمتها $a$ في المجموعة $b\text{.}$ ولاحظ أنّنا نبحث فحسب عن تطابقٍ لـ $A\text{;}$ إذ يجب أن تُوجد كلُّ قيمةٍ في المجموعات مرّةً واحدةً بالضبط.

سيكون لدينا تطابقٌ إذا تحقّق شرطُ التطابق. فلكلّ مجموعةٍ من قيم البطاقات (أي مجموعة $S \subseteq A$) يجب أن نبيّن أنّ $|N(S)| \ge |S|\text{.}$ أي إنّ عدد المجموعات التي تحوي تلك القيم لا يقلّ عن عدد القيم المختلفة. لكنّ ماذا لو لم يكن كذلك؟ لنقل إنّ $|S| = k\text{.}$ فإن كان $|N(S)| \lt k\text{,}$ لكان في تلك المجموعات أقلّ من $4k$ بطاقةً مختلفة (إذ إنّ كلّ مجموعةٍ تحوي 4 بطاقات). لكنّ هناك $4k$ بطاقةً ذات القيم $k$ المختلفة، لذا لا بدّ أن تكون إحدى هذه البطاقات في مجموعةٍ أخرى، وهذا تناقض. إذن يتحقّق شرطُ التطابق، ومن ثمّ يوجد تطابق، كما هو مطلوب.