אלגוריתמים 2 – תרגול 5
שידוכים בגרפים
הרחבות למשפט הול
הוכחה: נוסיף לd B קודקודים חדשים, שמחוברים לכל A.
=> A מקיים את תנאי הול => יש שידוך שמספק את כל A.
=> מתוך השידוך הזה, מקסימום d צלעות מחוברות לקודקודים החדשים
=> אם נקח את שאר הצלעות נקבל שידוך עבור כל הקודקודים בA מלבד לכל היותר d.
תזכורת - משפט tutte:
המשך ההוכחה
Tutte => Hall
X
Y
v
X
Y’
v
X
Y’
זוגי – זוגי = זוגי
v
X
Y’
הוכחה:
נניח ש G מקיים את תנאי hall
=> לפי למה 2 נובע כי X מקיים את תנאי tutte בH.
=> מ tutte נקבל כי H מכיל שידוך מושלם.
=> לפי למה 1, יש ב G שידוך שמספק את X.
הגדרה: בגרף קשיר G, צלע e נקראת ״גשר״ (או: צלע-חתך) אם {e}/G לא קשיר.
הגדרה: בגרף קשיר G, צלע e נקראת ״גשר״ (או: צלע-חתך) אם {e}/G לא קשיר.