Question

max_flow
spring_18_a

נתונה ליגת כדורסל עם nn קבוצות T={t1,,tn}T = \{t_1, \ldots, t_n\}. בנקודת זמן מסוימת במהלך העונה אנו מעוניינים לדעת אם לקבוצה מסוימת קיים עדיין סיכוי תאורטי לסיים את העונה במקום הראשון, כלומר שמספר הניצחונות הסופי שלה יהיה גדול ממש ממספר הניצחונות של כל קבוצה אחרת.

נסמן ב-w(i)w(i) את מספר הניצחונות של הקבוצה ה-ii בנקודת הזמן הנתונה, וב-p(i,j)p(i, j) את מספר המשחקים שנותרו עד סיום העונה בין הקבוצות tit_i ו-tjt_j.

כדי לתאר תרחיש עתידי, נסמן ב-w~(i,j)\tilde{w}(i, j) את מספר הניצחונות העתידיים של הקבוצה ה-ii על הקבוצה ה-jj. שימו לב ש-0w~(i,j)p(i,j)0 \leq \tilde{w}(i, j) \leq p(i, j).

א. נתון הקלט הבא:

pt1t2t3wt1414t2423t3122 \begin{array}{|l|l|l|l||l|} \hline p & t_1 & t_2 & t_3 & w \\\hline t_1 & - & 4 & 1 & 4 \\\hline t_2 & 4 & - & 2 & 3 \\\hline t_3 & 1 & 2 & - & 2 \\\hline \end{array}
  • האם לקבוצה t1t_1 סיכוי תאורטי לסיים ראשונה? אם כן רשמו ערכי w~\tilde{w} מתאימים עבור כל זוג קבוצות, אם לא מספיק לרשום "לא".

  • האם לקבוצה t2t_2 סיכוי תאורטי לסיים ראשונה? אם כן רשמו ערכי w~\tilde{w} מתאימים עבור כל זוג קבוצות, אם לא מספיק לרשום "לא".
  • האם לקבוצה t3t_3 סיכוי תאורטי לסיים ראשונה? אם כן רשמו את ערכי w~\tilde{w} מתאימים עבור כל זוג קבוצות, אם לא מספיק לרשום "לא".

נסמן ב-pp את מספר המשחקים הכולל שנשארו עד סיום העונה, כלומר:

p=1i<jnp(i,j) p = \sum_{1 \leq i < j \leq n}p(i, j)

וב-p(i)p(i) את מספר המשחקים הכולל שנותרו לקבוצה ה-ii עד סיום העונה, כלומר:

p(i)=j̸=ip(i,j) p(i) = \displaystyle{\sum_{j \neq i} p(i, j)}

נשים לב שמספר הניצחונות המרבי שהקבוצה ה-ii יכולה להשיג עד סוף העונה הוא w(i)+p(i)w(i) + p(i).

ב. נתונה ליגה עם 4 קבוצות, {t1,t2,t3,t4}\{t_1, t_2, t_3, t_4\}. נניח שהחל מנקודת זמן מסוימת במהלך העונה קבוצה t4t_4 מנצחת את כל המשחקים הנותרים. הביעו את הערכים הבאים באמצעות w(i)w(i)ו-p(i)p(i) המתאימים.

  • מספר הניצחונות הכולל של קבוצה t4t_4 בסיום העונה:
  • מספר המשחקים המקסימלי שקבוצה t3t_3 יכולה עוד לנצח עד סוף העונה כך שמספר הניצחונות הכולל שלה יהיה קטן ממש ממספר הניצחונות הכוללשל קבוצהt4t_4 בסיום העונה:

ג. נתונה ליגה עם 4 קבוצות, {t1,t2,t3,t4}\{t_1, t_2, t_3, t_4\}, ונתונה רשת הזרימה הבאה. קבעו קיבולים על הקשתות כך שזרימת המקסימום ברשת היא (pp(4))(p - p(4)) אמ"מ לקבוצה t4t_4 יש סיכוי תאורטי לסיים את העונה עם מספר הניצחונות הגדול (ממש) ביותר. יש להביע את הקיבולים במונחים של w(i)w(i), p(i)p(i) ו-p(i,j)p(i, j).

tikz

ד. תארו אלגוריתם שבהינתן T={t1,,tn}T = \{t_1, \ldots, t_n\}, w(i)w(i), p(i,j)p(i,j) וקבוצה tkt_k כמתואר לעיל, מחשב תרחיש שבו הקבוצה tkt_k מסיימת את העונה במקום הראשון, או קובע שאין תרחיש כזה. יש לנתח סיבוכיות ולהוכיח נכונות.

1

Answers

א.

  • כן.
    • w~(1,2)=4\tilde{w}(1,2) = 4
    • w~(1,3)=1\tilde{w}(1,3) = 1
    • w~(2,3)=2\tilde{w}(2,3) = 2
  • כן.
    • w~(2,1)=4\tilde{w}(2,1) = 4
    • w~(2,3)=2\tilde{w}(2,3) = 2
    • w~(3,1)=1\tilde{w}(3,1) = 1
  • לא. נשים לב שלא משנה איך נחלק את הניצחונות במשחקים הנותרים בין קבוצות t1t_1 ו-t2t_2 תמיד לאחת מהן יהיו יותר ניצחונות בסיום העונה, גם אם t3t_3 תנצח את כל המשחקים הנותרים שלה.

ב.

  • p(4)+w(4)p(4) + w(4)
  • p(4)+w(4)w(3)1p(4) + w(4) - w(3) - 1

ג.

tikz

ד. טענה: עבור רשת הזרימה N=(G,s,t,c)N = (G, s, t, c) המתוארת בהמשך לקבוצה tkt_k קיים סיכוי תאורטי לנצח אמ"מ זרימת המקסימום היא pp(k)p - p(k).

כאשר:

G=(V,E)G = (V, E)

V={s}TijTi{t}V = \{s\} \cup T_{ij} \cup T_i \cup \{t\}

Tij={titj}1i<jn:i,j̸=kT_{ij} = \{t_it_j\}_{1 \leq i < j \leq n : i,j \neq k}

Ti={ti}i[n]{k}T_i = \{t_i\}_{i \in [n] \setminus \{k\}}

E={s}×Tij{(titj,ti),(titj,tj)}1i<jn:i,j̸=kTi×{t}E = \{s\} \times T_{ij} \cup \{(t_it_j, t_i), (t_it_j, t_j)\}_{1 \leq i < j \leq n : i,j \neq k} \cup T_i \times \{t\}

c(s,titj)=p(i,j),c(titj,ti)=c(titj,tj)=,c(ti,t)=p(k)+w(k)w(i)1c(s, t_it_j) = p(i, j), c(t_it_j, t_i) = c(t_it_j, t_j) = \infty, c(t_i, t) = p(k) + w(k) - w(i) - 1

הוכחה: נראה התאמה חח"ע בין זרימה לתרחיש מנצח:

  • f(s,titj)=p(i,j)f(s, t_it_j) = p(i, j)
  • f(titj,ti)=w~(i,j)f(t_it_j, t_i) = \tilde{w}(i, j)
  • f(titj,tj)=w~(j,i)f(t_it_j, t_j) = \tilde{w}(j, i)
  • f(ti,t)=w~(i)f(t_i, t) = \tilde{w}(i)

נשים לב שאם אכן זהו תרחיש מנצח אז לפי האבחנות בסעיפים הקודמים חוק הקשת מתקיים, בנוסף, חוק הצומת מתקיים מהגדרה p(i,j)=w~(i,j)+w~(j,i)p(i, j) = \tilde{w}(i, j) + \tilde{w}(j, i) ומהאבחנה שסך הזרימה שנכנסת לצומת tit_i היא בדיוק מספר הניצחונות העתידיים שלה w~(i)\tilde{w}(i). מצד שני, אם ערך הזרימה הוא pp(k)p - p(k) אז נשים לב שכל הקשתות שיוצאות מ-ss רוויות ולכן מתקיים ש-p(i,j)=w~(i,j)+w~(j,i)p(i, j) = \tilde{w}(i, j) + \tilde{w}(j, i), בנוסף, בגלל פונקציית הקיבול, מתקיים שסך הניצחונות העתידיים של כל קבוצה קטן או שווה לסף שקבענו בסעיף הקודם, ולכן זהו אכן תרחיש מנצח.

אלגוריתם:

  • בנה את רשת הזרימה הנ"ל
  • חשב זרימת מקסימום ואם ערכה pp(k)p - p(k) פלוט תרחיש כמתואר בהוכחה, אחרת קבע ששוב אין סיכוי, אפילו לא תאורטי.

סיבוכיות: בניית הרשת לוקחת O(n2)O(n^2). מציאת הזרימה לוקח min{n6,n2(pp(k))}\min\{n^6, n^2(p - p(k))\} על ידי אלגוריתם אדמונדס קרפ, וזה גם זמן הריצה הכולל של האלגוריתם.

1
Feedback