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

:ניתן לראות, שבמקרה c שידוך המקסימום הוא גם שידוך מקסימלי, אך במקרים a ו-b השידוכים המקסימליים קטנים בגודלם משידוכי המקסימום בגרף שלהם, ועל כן אינם שידוכי מקסימום.

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

 

בעיית מציאת מספר השידוכים המושלמים ב[[גרף דו-צדדי]] היא שלמה ל-{{משמאל לימין|[[Sharp-P|#P]]}}, בעוד שבעיית ההכרעה המקבילה לה - השאלה האם בגרף דו-צדדי קיים שידוך מושלם - ניתנת לפתרון יעיל, כלומר ידוע שהיא שייכת ל-[[P (סיבוכיות)|P]].