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

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

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

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

• שידוך מקסימום שידוך מקסימום הוא שידוך מקסימלי בעל מספר הקשתות הרב ביותר מבין כלל השידוכים בגרף. הוא אוסף של קשתות $M$ בגרף, כך שלכל שידוך $M'$ אחר בגרף מתקיים $\left\vert M\right\vert \geq \left\vert M'\right\vert$.

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

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

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

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

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

ראו גם

• שידוך רב-ערכי

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

מדיה וקבצים בנושא שידוך בוויקישיתוף

• תורת השידוכים, דף שער בספרייה הלאומית
• שידוך, באתר MathWorld (באנגלית)