הוכחות מתמטיות/מתמטיקה בדידה/משפט החתונה של הול

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

בגרף דו-צדדי $\displaystyle G=(V_1,V_2,E)$ יש זיווג מושלם אם ורק אם לכל קבוצה $V_1S\subseteq$ מתקיים $\displaystyle |\Gamma(S)| \ge |S|$

[עריכה] הוכחה

זיווג מושלם של קבוצה אחת לשנייה מקביל להתאמה חד חד ערכית ועל. לא ניתן לעשות התאמה חד חד ערכית אם קיימת תת קבוצה שמספר האיברים בתמונתה קטן ממספר איבריה. לכן אם קיים זיווג מושלם ודאי שיתקיים $\displaystyle |\Gamma(S)| \ge |S|$ כאשר $Γ(S)$ היא קבוצת השכנים של של S

נניח שהתנאי מתקיים. ההוכחה באינדוקציה.

בסיס האינדוקציה: אם $\displaystyle |V_1| = |V_1| = n = 1$ קיימים שני קודקודים ובינהם צלע - הטענה מתקיימת.

נניח נכונות עבור $\displaystyle |V_1| = n-1$ ונוכיח עבור $\displaystyle |V_1'| = n$ .

תהא קבוצה חלקית ממש: $\displaystyle S \subseteq V_1'$ אם התנאי החזק יותר מתקיים מתקיים לכל תת קבוצה: $\displaystyle |\Gamma(S)| \ge |S| + 1$

אזי לכל קודקוד $x \in V_1'$ יש שני שכנים. $\displaystyle \Gamma(x)={y_1,y_2}$

נבחר באופן שרירותי אחד מהקודקודים ונסיר את הקודקודים $\displaystyle {x,y_1}$ ואת הצלעות החלות בהם, כך שנוצר גרף חדש:

$\hat{G} = G \setminus {\{x,y_1\}}$

כמובן שלכל תת קבוצה $S \subset V_1\setminus{{X}}$ מתקיים $\displaystyle |\Gamma(S)| \ge |S|$ ולפי הנחת האינדוקציה, זהו גרף עם זיווג מושלם. נוסיף לו את הזוג $x, y 1$ וזהו זיווג מושלם ב $\displaystyle G$

אם התנאי החזק לא מתקיים הרי שקיימת תת קבוצה חלקית ממש כך ש $\displaystyle |\Gamma(S)| = |S|$

(אם הקבוצה לא חלקית לכל קודקוד ב $V 1$ מתאים קודקוד יחיד ב $V 2$ , ואז המשפט מתקיים.)

נתבונון בתת הגרף $S \cup \Gamma(S)$ הוא עומד בתנאי משפט הול, ולפי הנחת האינדוקציה מכיל זיווג מושלם.

נותר לזווג את $V_1 \setminus S$ ל $V_2 \setminus \Gamma(S)$

מאחר ו $\displaystyle |\Gamma(S)| = |S|$ הרי שקבוצת הקודקודים הנותרת מקיימת את התנאי החזק יותר.

הוכחות מתמטיות/מתמטיקה בדידה/משפט החתונה של הול

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

[עריכה] הוכחה

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא