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

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

ניצור שתי קבוצות. הקבוצה השמאלית, תכיל בתחילה את כל הצמתים (כלומר ); הקבוצה הימנית, , תהיה ריקה בתחילה (כלומר ).

נאמר שקשת כלשהי שמחה אם ו שייכות לשתי קבוצות שונות. נגדיר כ את קבוצת הקשתות היוצאות מ, ונגדיר כ את קבוצת הקשתות השמחות היוצאות מ. לפי הגדרות אלו:

  1. בתחילה, אף קשת אינה שמחה. (.)
  2. אם לפחות חצי מהקשתות היוצאות מכל צומת שמחות, פתרנו את הבעיה. (אם , אז פתרנו את הבעיה.)

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



דוגמה:

בתרשים הבא, . לכן נעביר את ל.

העברת צומת והשפעתה.


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



משפט:

בכל פעם שמעבירים צומת כלשהו כמתואר לעיל, עולה מספר הקשתות השמחות.


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

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

הוכחה: נניח שהשכנים של בקבוצה שלו הם , ושכניו בקבוצה השניה הם . נשים לב שבהכרח .

לאחר העברת , מספר הקשתות השמחות גדל ב.

מש"ל.PNG