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