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