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