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

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

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

• שידוך מקסימום הוא שידוך שגדול לפחות כמו כל שידוך אחר שקיים בגרף.

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

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

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