משפט החתונה
מתוך ויקיפדיה, האנציקלופדיה החופשית
בקומבינטוריקה, משפט החתונה, שמיוחס למתמטיקאי פיליפ הול, הוא משפט שנותן תנאי הכרחי ומספיק לבחירת נציגים ייחודיים עבור משפחה של קבוצות.
הדוגמה המקובלת למשפט שנתנה לו את שמו היא כדלהלן: נניח שיש לנו
נשים ו-
גברים. כל אישה מעוניינת בחלק מהגברים - כלומר, לכל אישה ניתן להתאים קבוצה של גברים שבהם היא מעוניינת - ואילו כל גבר ישמח לקבל כל אישה שתרצה אותו. השאלה הנשאלת היא האם יש דרך לחתן את כל הנשים כך שכולן יקבלו גבר שבו הן מעוניינות. בצורה פורמלית יותר, השאלה היא האם מכל אחת מהקבוצות שהתאמנו לנשים ניתן לבחור נציג (בעל) כך שאותו נציג לא ייבחר פעמיים עבור שתי קבוצות (נשים) שונות. משפט החתונה מספק את התנאי הדרוש כדי שניתן יהיה לעשות זאת.
[עריכה] ניסוח פורמלי
תהא
משפחה של קבוצות. קבוצת נציגים ייחודיים של המשפחה הזו היא קבוצה של איברים
כך שכל שני איברים שונים זה מזה,
וכל איבר שייך לקבוצה אחרת,
(איבר זה הוא הנציג של אותה קבוצה).
על פי משפט החתונה, תנאי הכרחי ומספיק לקיום של קבוצת נציגים ייחודיים למשפחת קבוצות נתונה הוא שלכל תת קבוצה של המשפחה,
יתקיים
, כלומר בכל
קבוצות שונות של המשפחה יש לפחות
איברים שונים בכל הקבוצות.
קל לראות שהתנאי הכרחי - אם עבור
קבוצות כלשהן יש פחות מ
איברים שונים, בהכרח כל בחירת נציגים עבור הקבוצות תהיה כזו שבה נציג אחד נבחר לפחות פעמיים.
המשפט ניתן להרחבה גם עבור מספר אינסופי של קבוצות, תוך שימוש בלמה של צורן.
[עריכה] ניסוח עבור גרפים
דרך אחרת לנסח את המשפט היא עבור גרפים דו צדדיים. אם
הוא גרף דו צדדי ששתי הקבוצות המרכיבות אותו שוות בגודלן, אז קיים בו שידוך מושלם אם ורק אם לכל תת קבוצה
מתקיים
, כאשר
הוא אוסף השכנים של צמתים ב-
. הדמיון לניסוח הקודם ברור - הקבוצה
מייצגת את משפחת הקבוצות שעבורן בוחרים נציגים, הקבוצה
את אוסף האיברים שהקבוצות במשפחה יכולות להכיל, וקשת מייצג קשר של הכלה.
[עריכה] מספר האפשרויות
מהוכחת המשפט ניתן גם לתת חסם תחתון למספר האפשרויות שבהן ניתן לבחור נציגים ייחודיים. אם
הוא גודלה המינימלי של הקבוצה הקטנה מכל הקבוצות ו-
הוא מספר הקבוצות, הרי שאם מתקיים
, מספר האפשרויות הוא לפחות
אפשרויות. אם
, הרי שיש לפחות
אפשרויות. נשים לב כי זהו חסם נמוך מאוד, ולעתים קרובות מספר האפשרויות גדול ממנו בהרבה.

