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

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

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

• שידוך מקסימום הוא אוסף של קשתות M בגרף G עם התכונה שהוספת כל קשת שאינה בM לM תגרום לכך שM כבר לא יהיה שידוך, כלומר M תייצג שידוך מקסימום אם עבור כל קשת בG יש הצטלבות לא ריקה עם קשת אחת מM. דוגמאות לשידוך מקסימום (באדום):

• שידוך מקסימלי הוא שידוך שלא ניתן להגדיל אותו על ידי הוספת קשתות נוספות. שידוך מקסימום הוא שידוך מקסימלי, אך ההפך אינו בהכרח נכון. דוגמאות לשידוך מקסימלי:

ניתן לראות, שבמקרה c השידוך המקסימלי הוא גם שידוך מקסימום, אך במקרים a ו-b השידוכים המקסימליים קטנים בגודלם משידוכי המקסימום בגרף שלהם, ועל כן אינם שידוכי מקסימום.

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

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

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

מספר השידוכים בגרף שלם של $K_{n+1}$ עבור n אי זוגי ניתן לביטוי באמצעות עצרת כפולה: לכל קודקוד יש n אפשרויות שידוך, ולאחר שבוחרים שידוך לקודקוד אחד עם אחר נותר לבחור שידוך ליתר הקודקודים מלבד שני אלו ששודכו. לדוגמה בגרף שלם של ארבעה קודקודים, א', ב', ג' וד' יש שלושה שידוכים מושלמים: א+ב וג+ד, א+ג וב+ד, וא+ד וב+ג.