שידוך (תורת הגרפים)

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

  • שידוך מקסימום[1] הוא שידוך שגדול לפחות כמו כל שידוך אחר שקיים בגרף. דוגמאות לשידוך מקסימום:
דוגמאות לשידוך מקסימום
  • שידוך מקסימלי הוא שידוך שלא ניתן להגדיל אותו על ידי הוספת קשתות נוספות. שידוך מקסימום הוא שידוך מקסימלי, אך ההפך אינו בהכרח נכון. דוגמאות לשידוך מקסימלי:
דוגמאות לשידוך מקסימלי
ניתן לראות, שבמקרה c השידוך המקסימלי הוא גם שידוך מקסימום, אך במקרים a ו-b השידוכים המקסימליים קטנים בגודלם משידוכי המקסימום בגרף שלהם, ועל כן אינם שידוכי מקסימום.
  • שידוך מושלם הוא שידוך שבו משתתפים כל הצמתים בגרף. כלומר, הוא חלוקה של צמתי הגרף לזוגות, כך שכל זוג צמתים מקושר על ידי קשת. לעתים מגדירים שידוך מושלם גם בגרף עם מספר אי-זוגי של צמתים; במקרה זה מתירים לצומת אחד להישאר ללא בן זוג (כלומר, לא להיות מכוסה על ידי אף קשת בשידוך). משפט החתונה נותן תנאי הכרחי ומספיק לכך שיהיה שידוך מושלם בגרף דו-צדדי. עבור גרפים כלליים, משפט טט (Tutte) מגדיר הכללה לקיום שידוך מושלם.


בעיית מציאת מספר השידוכים המושלמים בגרף דו-צדדי היא שלמה ל-#P, בעוד שבעיית ההכרעה המקבילה לה - השאלה האם בגרף דו-צדדי קיים שידוך מושלם - ניתנת לפתרון יעיל, כלומר ידוע שהיא שייכת ל-P.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ בספר מבוא לאלגוריתמים של קורמן בתרגום האו"פ מכונה שידוך מקסימלי. ראה כרך ב' עמוד 197 הדפסה שנייה