מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/גרפים וייצוגיהם/תרגילים/הושבה משני צידי שולחן/תשובה

ניצור שתי קבוצות. הקבוצה השמאלית, $\displaystyle L$ תכיל בתחילה את כל הצמתים (כלומר $\displaystyle L=V$); הקבוצה הימנית, $\displaystyle R$, תהיה ריקה בתחילה (כלומר $\displaystyle R=\emptyset$).

נאמר שקשת כלשהי $\displaystyle e=(u,v)$ שמחה אם $\displaystyle u$ ו$\displaystyle v$ שייכות לשתי קבוצות שונות. נגדיר כ $\displaystyle E(u)$ את קבוצת הקשתות היוצאות מ$\displaystyle u$, ונגדיר כ$\displaystyle H(u)$ את קבוצת הקשתות השמחות היוצאות מ$\displaystyle u$. לפי הגדרות אלו:

1. בתחילה, אף קשת אינה שמחה. ($\displaystyle \forall _{u\in U}|H(u)|=\emptyset$.)
2. אם לפחות חצי מהקשתות היוצאות מכל צומת שמחות, פתרנו את הבעיה. (אם $\displaystyle \forall _{u\in U}|H(u)|\geq {\frac {|E(u)|}{2}}$, אז פתרנו את הבעיה.)

כעת, כל עוד לא פתרנו את הבעיה, נפעל כדלהלן. נבחר שרירותית צומת כלשהו $\displaystyle u$ מבין הצמתים שרוב קשתותיהם אינו שמח. נעביר את $\displaystyle u$ לקבוצה השניה.

דוגמה: בתרשים הבא, $\displaystyle |H(u)|=2<{\frac {|E(u)|}{2}}={\frac {5}{2}}$. לכן נעביר את $\displaystyle u$ ל$\displaystyle R$. העברת צומת והשפעתה.

המשפט הבא מראה שהתהליך הוא סופי.

משפט: בכל פעם שמעבירים צומת כלשהו $\displaystyle u$ כמתואר לעיל, עולה מספר הקשתות השמחות.

לפני הוכחת משפט זה, הבה נבין מדוע הוא מראה שהתהליך סופי. המשפט טוען שכל עוד קיים צומת כלשהו $\displaystyle u$ שרוב קשתותיו אינו שמח - העברת $\displaystyle u$ לקבוצה השניה תגדיל את מספר הקשתות השמחות. מספר הקשתות השמחות מתחיל ב0, ויכול להגיע לכל היותר ל$\displaystyle |E|$.

כעת נוכיח את המשפט.

הוכחה: נניח שהשכנים של $\displaystyle u$ בקבוצה שלו הם $\displaystyle u_{1},\ldots ,u_{i}$, ושכניו בקבוצה השניה הם $\displaystyle v_{1},\ldots ,v_{j}$. נשים לב שבהכרח $\displaystyle i>j$.

לאחר העברת $\displaystyle u$, מספר הקשתות השמחות גדל ב$\displaystyle i-j\geq 1$.