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