הצגת המקור של הדף "שידוך (תורת הגרפים)"

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

לשידוכים חשיבות רבה בתורת הגרפים, והם מתקשרים באופן טבעי לבעיות רבות (למשל ל[[בעיית הנישואים היציבים]]). ישנם מספר סוגים מיוחדים של שידוכים:
* '''שידוך מקסימלי''' הוא שידוך שלא ניתן להגדיל אותו על ידי הוספת קשתות נוספות. שידוך מקסימום הוא שידוך מקסימלי, אך ההפך אינו בהכרח נכון. דוגמאות לשידוך מקסימלי (הקשתות בקבוצת הזיווג מסומנות באדום):
: [[קובץ:Maximal-matching.svg|דוגמאות לשידוך מקסימלי]]
*'''שידוך מקסימום'''{{הערה|בספר מבוא לאלגוריתמים של קורמן בתרגום האו"פ מכונה שידוך מקסימלי. ראה כרך ב' עמוד 197 הדפסה שנייה}} שידוך מקסימום הוא שידוך מקסימלי בעל מספר הקשתות הרב ביותר מבין כלל השידוכים בגרף. הוא אוסף של קשתות <math>M</math> בגרף, כך שלכל שידוך <math>M'</math> אחר בגרף מתקיים <math>\left\vert M \right\vert \geq \left\vert M' \right\vert</math>.
: [[קובץ:Maximum-matching-labels.svg|דוגמאות לשידוך מקסימום]]
:ניתן לראות, שבמקרה c השידוך המקסימלי הוא גם שידוך מקסימום, אך במקרים a ו-b השידוכים שהוצגו בפסקה הקודמת קטנים בגודלם משידוכי המקסימום בגרף שלהם, על אף שהם מקסימליים, ועל כן אינם שידוכי מקסימום.
:שידוך מקסימלי ניתן למציאה על ידי אלגוריתם חמדן פשוט. שידוך מקסימום הוא גם שידוך מקסימלי, לכן ניתן למצוא שידוך גדול ביותר בזמן פולינומי. עם זאת, אין אלגוריתם פולינומי ידוע עבור מציאת שידוך מינימלי, כלומר שידוך מקסימלי שמכיל את המספר הקטן ביותר של קשתות.
* '''שידוך מושלם''' הוא שידוך שבו משתתפים כל הצמתים בגרף. כלומר, הוא [[חלוקה (תורת הקבוצות)|חלוקה]] של צמתי הגרף לזוגות, כך שכל זוג צמתים מקושר על ידי קשת. לעיתים מגדירים שידוך מושלם גם בגרף עם מספר אי-זוגי של צמתים; במקרה זה מתירים לצומת אחד להישאר ללא בן זוג (כלומר, לא להיות מכוסה על ידי אף קשת בשידוך). [[משפט החתונה]] נותן [[תנאי הכרחי ומספיק]] לכך שיהיה שידוך מושלם ב[[גרף דו-צדדי]]. עבור גרפים כלליים, [[משפט טט]] (Tutte) מגדיר הכללה לקיום שידוך מושלם. ניתן לראות, שבמקרה b השידוך מקסימום הוא גם שידוך מושלם.
* '''שידוך כמעט מושלם''' הוא שידוך שבו אין שידוך בדיוק לקודקוד אחד. גרף יכול להכיל שידוך כמעט מושלם רק כאשר לגרף יש מספר אי זוגי של קודקודים, ושידוך כמעט מושלם הוא גם שידוך מקסימום. באיור לעיל, חלק c מציג שידוך כמעט מושלם. 

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

מספר השידוכים ב[[גרף שלם]] של <math>K_{n+1}</math> עבור n אי זוגי ניתן לביטוי באמצעות [[עצרת כפולה]]: לכל קודקוד יש n אפשרויות שידוך, ולאחר שבוחרים שידוך לקודקוד אחד עם אחר נותר לבחור שידוך ליתר הקודקודים מלבד שני אלו ששודכו. לדוגמה בגרף שלם של ארבעה קודקודים, א', ב', ג' וד' יש שלושה שידוכים מושלמים: א+ב וג+ד, א+ג וב+ד, וא+ד וב+ג.

==ראו גם==
* [[שידוך רב-ערכי]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{דף שער בספרייה הלאומית|987007555888405171|תורת השידוכים}}
* {{MathWorld}}

==הערות שוליים==
{{הערות שוליים}}

{{תורת הגרפים}}
{{בקרת זהויות}}

[[קטגוריה:תורת הגרפים]]