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

