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

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

: [[קובץ:Maximal-matching.svg|דוגמאות לשידוך מקסימלי]]

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