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

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

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

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

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

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

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

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

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

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