משפט החתונה

בקומבינטוריקה, משפט החתונה, שמיוחס למתמטיקאי האנגלי פיליפ הול (1935), הוא משפט שמגדיר תנאי הכרחי ומספיק לבחירת נציגים ייחודיים עבור משפחה של קבוצות.

נניח שיש לנו שתי קבוצות זרות, "קבוצת הנשים" ו"קבוצת הגברים", וכל אישה מעוניינת בחלק מהגברים. נשאלת השאלה, באילו תנאים ניתן לשדך לכל אחת מהנשים גבר יחיד שהיא מעוניינת בו (באופן מונוגמי). ברור כי תנאי הכרחי הוא שמספר הגברים יהיה לפחות כמספר הנשים. ניתן להכליל דרישה זו לכל תת-קבוצה של הנשים. כלומר, תנאי הכרחי הוא שכל ${\displaystyle k}$ נשים תהיינה מעוניינות (יחדיו) בלפחות ${\displaystyle k}$ גברים. משפט החתונה של הול טוען כי זהו גם תנאי מספיק.

ניסוח פורמלי

תהא ${\displaystyle \{S_{1},\dots ,S_{n}\}}$ משפחה של קבוצות סופיות שאינן בהכרח זרות זו לזו. קבוצת נציגים ייחודיים של המשפחה הזו היא קבוצה של איברים ${\displaystyle a_{1},\dots ,a_{n}}$ כך שכל שני איברים שונים זה מזה, ${\displaystyle i\neq j\Rightarrow a_{i}\neq a_{j}}$, וכן ${\displaystyle a_{i}\in S_{i}}$ (איבר זה הוא הנציג של אותה קבוצה).

על פי משפט החתונה, תנאי הכרחי ומספיק לקיום של קבוצת נציגים ייחודיים למשפחת קבוצות נתונה הוא שלכל תת-קבוצה של המשפחה, ${\displaystyle T=\left\{S_{i_{1}},\dots ,S_{i_{t}}\right\}}$ יתקיים ${\displaystyle ,\left|\cup S_{i_{k}}\right|\geq t}$ כלומר בכל ${\displaystyle t}$ קבוצות שונות של המשפחה יש לפחות ${\displaystyle t}$ איברים שונים בכל הקבוצות.

קל לראות שהתנאי הכרחי - אם עבור ${\displaystyle t}$ קבוצות כלשהן יש פחות מ-${\displaystyle t}$ איברים שונים, בהכרח כל בחירת נציגים עבור הקבוצות תהיה כזו שבה נציג אחד נבחר לפחות פעמיים.

המשפט ניתן להרחבה גם עבור מספר אינסופי של קבוצות, תוך שימוש בלמה של צורן.

למשפט יש גם הרבה שימושים מעניינים שאינם קשורים ישירות לשידוכים. לדוגמה, בהינתן חפיסת קלפים סטנדרטית, שמחולקת באופן שרירותי ל-13 רביעיות, ניתן להראות באמצעות משפט החתונה שניתן לבחור קלף אחד בדיוק מכל רביעייה כך ש-13 הקלפים הנבחרים יכילו בדיוק קלף אחד מכל 'מספר' (אס, 2, 3, 4, 5, 6, 7, 8, 9, 10, נסיך, מלכה ומלך).

ניסוח עבור גרפים

דרך אחרת לנסח את המשפט היא עבור גרפים דו צדדיים. אם ${\displaystyle \ G=(S,T,E)}$ הוא גרף דו צדדי, אז קיים בו שידוך המכסה את צד ${\displaystyle \ S}$ אם ורק אם לכל תת-קבוצה ${\displaystyle \ X\subseteq S}$ מתקיים ${\displaystyle |X|\leq |N_{G}(X)|}$, כאשר ${\displaystyle \ N_{G}(X)}$ הוא אוסף השכנים של צמתים ב-${\displaystyle \ X}$. השקילות לניסוח הקודם קלה להוכחה - הקבוצה ${\displaystyle \ S}$ מייצגת את משפחת הקבוצות שעבורן בוחרים נציגים, הקבוצה ${\displaystyle \ T}$ את אוסף האיברים שהקבוצות במשפחה יכולות להכיל, וקשת מייצגת קשר של הכלה.

הוכחות

הוכחה באמצעות מסלולים מרחיבים

ההוכחה היא לפי הניסוח של המשפט עבור שידוך בגרף דו צדדי.

${\displaystyle (\Leftarrow )}$ נתון גרף דו צדדי ${\displaystyle \ G}$ עם צדדים ${\displaystyle \ S,T}$ ונניח שהשידוך המקסימלי מכסה את כל הקודקודים ${\displaystyle \ S}$. נראה שלכל ${\displaystyle S'\subseteq S}$ מתקיים ${\displaystyle |N(S')|\geq |S'|}$:

נסמן ב-${\displaystyle \ M}$ שידוך שמכסה את כל הקודקודים ב-${\displaystyle \ S}$. תהי ${\displaystyle M(S')}$ קבוצת כל הקודקודים ב-${\displaystyle \ T}$ שהותאמו לקבוצה נתונה ${\displaystyle S'\subseteq S}$. על פי הגדרת שידוך, ${\displaystyle |M(S')|=|S'|}$. היות שכל האיברים ב-${\displaystyle M(S')}$ הם שכנים של ${\displaystyle S'}$, מתקיים ${\displaystyle M(S')\subseteq N_{G}(S')}$ ולכן, ${\displaystyle |M(S')|\leq |N_{G}(S')|}$. מכך יוצא ש-${\displaystyle |S'|\leq |N_{G}(S')|}$.

${\displaystyle (\Rightarrow )}$ נתון גרף דו צדדי ${\displaystyle \ G}$ עם צדדים ${\displaystyle \ S,T}$ ונניח את תנאי המשפט - לכל ${\displaystyle S'\subseteq S}$ מתקיים ש-${\displaystyle |N(S')|\geq |S'|}$.

נסתכל על שידוך בגודל מקסימלי ${\displaystyle \ M}$ לצמתי ${\displaystyle \ S}$. נסמן את הצמתים שאינם משודכים ב-${\displaystyle \ S}$ על ידי ${\displaystyle {\tilde {S}}}$. נניח בשלילה ש ${\displaystyle {\tilde {S}}\neq \emptyset }$.

מסלול מרחיב הוא מסלול (שיכול להיות ריק) ${\displaystyle \ P=(v_{1},v_{2},...,v_{n})}$ בגרף המתחיל בצומת מ-${\displaystyle \ {\tilde {S}}}$ כך שהקשתות האי זוגיות ${\displaystyle \ (v_{2i-1},v_{2i})}$ שייכות ל-${\displaystyle \ E-M}$ והקשתות הזוגיות ${\displaystyle \ (v_{2i},v_{2i+1})}$ שייכות ל ${\displaystyle \ M}$.

נניח שקיים מסלול מרחיב ${\displaystyle P}$ המסתיים בצומת ב-${\displaystyle \ T}$ שאינו משודך. נוכל להגדיר שידוך חדש ${\displaystyle M'=M\triangle P}$ שגודלו יהיה לפחות ${\displaystyle \ |M|+1}$ בסתירה לכך שהשידוך ${\displaystyle \ M}$ הוא מגודל מקסימלי. לכן כל מסלול מרחיב שמסתיים ב ${\displaystyle \ T}$ חייב להסתיים בצומת ששייך לשידוך ${\displaystyle \ M}$.

נגדיר את ${\displaystyle S'\subseteq S}$ להיות כל הצמתים מ-${\displaystyle \ S}$ שניתן להגיע אליהם עם מסלולים מרחיבים ונסמן ${\displaystyle \ T'=N(S')}$.

נניח שקיים ${\displaystyle \ u\in T'}$ שאינו משודך. אז הוא שכן של ${\displaystyle v\in S'}$ כלשהו, ובנוסף הקשת ${\displaystyle \ e_{1}}$ המחברת ביניהם אינה שייכת לשידוך. לפי הגדרת ${\displaystyle S'}$, קיים מסלול מרחיב ${\displaystyle P}$ המגיע ל-${\displaystyle v}$. לאחר הוספת הקשת ${\displaystyle \ e_{1}}$ מקבלים מסלול מרחיב המגיע ל-${\displaystyle u}$, בסתירה לטענה שהוכחנו קודם לכן. קיבלנו, אם כן, ש-${\displaystyle \ T'}$ מכיל רק צמתים משודכים ב-${\displaystyle M}$. מפני שצמתי ${\displaystyle {\tilde {S}}}$ אינם משודכים, נובע שהצמתים המשודכים אל ${\displaystyle \ T'}$ נמצאים ב-${\displaystyle S'-{\tilde {S}}}$. נוכל איפוא לרשום:

${\displaystyle \ |S'|=|S'-{\tilde {S}}|+|{\tilde {S}}|\geq |T'|+|{\tilde {S}}|>|T'|=|N(S')|}$

ומקבלים סתירה לכך ש-${\displaystyle |S'|\leq |N(S')|}$. ${\displaystyle \square }$

הוכחה באינדוקציה

נוכיח את הכיוון הקשה ${\displaystyle (\Rightarrow )}$ בלבד, לפי הניסוח של המשפט עבור שידוך בגרף דו צדדי. נתון גרף דו צדדי ${\displaystyle \ G}$ עם צדדים ${\displaystyle \ S,T}$ ונניח את תנאי המשפט - לכל ${\displaystyle S'\subseteq S}$ מתקיים ש-${\displaystyle |N(S')|\geq |S'|}$. נוכיח שקיים שידוך ב-${\displaystyle G}$ המכסה את ${\displaystyle S}$.

ההוכחה תתבצע באינדוקציה שלמה על הגודל ${\displaystyle |S|}$. בבסיס האינדוקציה נניח כי ${\displaystyle |S|=1}$. נסמן ב-${\displaystyle u}$ את הצומת היחיד ב-${\displaystyle S}$. מכיוון ש-${\displaystyle |N(S)|\geq |S|=1}$, יש ל-${\displaystyle u}$ שכן ${\displaystyle v\in T}$. הקשת ${\displaystyle uv}$ היא שידוך המכסה את ${\displaystyle S}$.

כעת נניח כי ${\displaystyle |S|=n>1}$ וכי הטענה נכונה כאשר ${\displaystyle |S|<n}$. נאמר שתת-קבוצה ${\displaystyle {\tilde {S}}\subset S}$ היא הדוקה אם ${\displaystyle {\tilde {S}}\neq \emptyset ,S}$ וגם ${\displaystyle |N({\tilde {S}})|=|{\tilde {S}}|}$. נפריד לשני מקרים.

מקרה 1. לא קיימת תת-קבוצה הדוקה ${\displaystyle {\tilde {S}}\subset S}$. נבחר צומת כלשהו ${\displaystyle u\in S}$. אז יש ל-${\displaystyle u}$ שכן ${\displaystyle v\in T}$. נסמן ${\displaystyle S_{1}=S-\{u\}}$ ו-${\displaystyle T_{1}=T-\{v\}}$. כעת נגדיר גרף דו-צדדי ${\displaystyle G_{1}}$ בתור תת-הגרף המושרה של ${\displaystyle G}$ עם צדדים ${\displaystyle S_{1},T_{1}}$. לכל תת-קבוצה ${\displaystyle S'\subset S_{1}}$ מתקיים

${\displaystyle |N_{G_{1}}(S')|\geq |N_{G}(S')|-1\geq |S'|+1-1=|S'|}$

לכן, מהנחת האינדוקציה, קיים שידוך ${\displaystyle M_{1}}$ ב-${\displaystyle G_{1}}$ המכסה את ${\displaystyle S_{1}}$. קבוצת הקשתות ${\displaystyle M_{1}\cup \{uv\}}$ היא שידוך ב-${\displaystyle G}$ המכסה את ${\displaystyle S}$.

מקרה 2. קיימת תת-קבוצה הדוקה ${\displaystyle {\tilde {S}}\subset S}$. נסמן ${\displaystyle {\tilde {T}}=N({\tilde {S}})}$. מהנחת האינדוקציה, קיים שידוך ${\displaystyle {\tilde {M}}}$ ב-${\displaystyle G}$ המכסה את ${\displaystyle {\tilde {S}}}$. תהיינה ${\displaystyle S_{1}=S-{\tilde {S}}}$ ו-${\displaystyle T_{1}=T-{\tilde {T}}}$. נגדיר גרף דו-צדדי ${\displaystyle G_{1}}$ בתור תת-הגרף המושרה של ${\displaystyle G}$ עם צדדים ${\displaystyle S_{1},T_{1}}$. לכל תת-קבוצה ${\displaystyle S'\subset S_{1}}$ מתקיים

${\displaystyle |S'|+|{\tilde {S}}|=|S'\cup {\tilde {S}}|\leq |N_{G}(S'\cup {\tilde {S}})|=|N_{G_{1}}(S')\cup {\tilde {T}}|=|N_{G_{1}}(S')|+|{\tilde {T}}|}$

מכיוון ש-${\displaystyle {\tilde {S}}}$ הדוקה, נובע ש-${\displaystyle |{\tilde {S}}|=|{\tilde {T}}|}$ ולכן ${\displaystyle |N_{G_{1}}(S')|\geq |S'|}$ לכל תת-קבוצה ${\displaystyle S'\subset S_{1}}$. מהנחת האינדוקציה, קיים שידוך ${\displaystyle M_{1}}$ ב-${\displaystyle G_{1}}$ המכסה את ${\displaystyle S_{1}}$. קבוצת הקשתות ${\displaystyle M_{1}\cup {\tilde {M}}}$ היא שידוך ב-${\displaystyle G}$ המכסה את ${\displaystyle S}$.

הוכחנו את צעד האינדוקציה בשני המקרים, מה שמשלים את ההוכחה. ${\displaystyle \square }$

מספר האפשרויות

מהוכחת המשפט ניתן גם לתת חסם תחתון למספר האפשרויות שבהן ניתן לבחור נציגים ייחודיים. אם ${\displaystyle t}$ הוא גודלה המינימלי של הקבוצה הקטנה מכל הקבוצות ו-${\displaystyle n}$ הוא מספר הקבוצות, הרי שאם מתקיים ${\displaystyle \!\,t\geq n}$, מספר האפשרויות הוא לפחות ${\displaystyle t\cdot (t-1)\cdot \dots \cdot (t-n+1)}$ אפשרויות. אם ${\displaystyle t<n}$, הרי שיש לפחות ${\displaystyle t!}$ אפשרויות. נשים לב כי זהו חסם נמוך מאוד, ולעיתים קרובות מספר האפשרויות גדול ממנו בהרבה.

בעיית מניית מספר האפשרויות שבהן ניתן לבחור נציגים ייחודיים, או מניית מספר השידוכים המושלמים בגרף דו צדדי, היא שלמה ל-#P.

ראו גם

• שידוך (תורת הגרפים)

קישורים חיצוניים

• משפט החתונה, באתר MathWorld (באנגלית)