שידוך (תורת הגרפים) – הבדלי גרסאות

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

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

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

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