Question

greedy
winter_15-16_a

נתון גרף G=(V,E)G = (V, E) לא מכוון, הציעו אלגוריתם המוצא חתך כך שלפחות מחצית מקשתות הגרף חוצות את החתך.

רמז: חישבו על אלגוריתם שמתחזק שתי קבוצות A1,A2A_1, A_2 שבהתחלה ריקות, ובסיום מכילות את קבוצות הצמתים בחתך המבוקש. כאשר צריך להוסיף צומת vv לאחת הקבוצות, איך כדאי לבחור אותה?

1

Answers

בהינתן תת קבוצה של צמתים AVA \subseteq V וצומת uVu \in V נסמן ב-e(u,A)={(u,v):vA}e(u, A) = \{(u, v) : v \in A\}.

אלגוריתם:

  • אתחל A1,A2A_1, A_2 \leftarrow \emptyset.
  • לכל צומת vVv \in V בסדר שרירותי
  • הוסף את vv ל-argminA{A1,A2}e(v,A)\displaystyle{\arg \min_{A \in \{A_1, A_2\}}|e(v, A)|}
  • החזר A1,A2A_1, A_2.

טענה: בזמן ריצת האלגוריתםA1,A2A_1, A_2 חתך שמקיים את התנאי ב-G[A1A2]G[A_1 \cup A_2].

הוכחה: באינדוקציה על צעד האלגוריתם.

בסיס: טריוויאלי.

צעד: כאשר מוסיפים צומת vv לאחת מהקבוצות, הקשתות שמתווספות לגרף הן בדיוק e(v,A1)e(v,A2)e(v, A_1) \cup e(v, A_2) ומכיוון שהאלגוריתם מוסיף את הצומת באופן כזה שלפחות חצי מהקשתות החדשות חוצות את החתך הטענה ממשיכה להתקיים.

1
Feedback