Question

spring_5_b
max_flow

nn משפחות {f1,,fn}\{f_1, \ldots, f_n\} מוזמנות לחתונה. נסמן ב-nin_i את מספר האנשים במשפחה fif_i לכל 1nn1 \leq n \leq n. על מנת לעודד הכרות בין האורחים מעוניינים החתן והכלה לפזר את המוזמנים בין השולחנות כך שבני אותה משפחה ישובצו לשולחנות שונים (כלומר, שלא יהיה מצב שבאותו שולחן יושבים שניים או יותר מאותה משפחה). מספר השולחנות הוא mm וסביב כל שולחן יכולים לשבת לכל היותר kk אנשים.

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

2

Answers

נראה רדוקציה לרשת זרימה:

פורמלית: N=(G=(V,E),s,t,c)N = (G = (V, E), s, t, c) כאשר

V={s,t}{fi}1in{ti}1imV = \{s,t\} \cup \{f_i\}_{1 \leq i \leq n} \cup \{t_i\}_{1 \leq i \leq m}

E=SMTE = S \cup M \cup T

S={sfi}1inS = \{sf_i\}_{1\leq i \leq n}

M={fitj}1in,1jmM = \{f_it_j\}_{1 \leq i \leq n, 1 \leq j \leq m}

T={tjt}1jmT = \{t_jt\}_{1 \leq j \leq m}

i,j  c(sfi)=ni,c(fifj),c(tjt)=k\forall i,j \; c(sf_i) = n_i, c(f_if_j), c(t_jt) = k

נסמן N=i=1nniN = \sum_{i = 1}^n n_iונראה התאמה חח"ע בין זרימה עם ערך NN להושבה חוקית של אורחים. קל לראות שלא תיתכן זרימה עם ערך גדול מ-NN.

תהה ff פונקציית זרימה עם ערך NN, נפזר את המשפחה fif_i בשולחנות {tj:f(fitj)=1}\{t_j : f(f_it_j) = 1\}.

נסמן ב-xij{0,1}x_ij \in \{0,1\} את מספר האנשים ממשפחה ii שהושבו בשולחן jj בפיזור חוקי כלשהו, ונגדיר.

f(sfi)=ni,f(fitj)=xij,f(tjt)=i=1nxijf(sf_i) = n_i, f(f_it_j) = x_{ij}, f(t_jt) = \sum_{i = 1}^n x_{ij}.

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

אלגוריתם:

  • מצא זרימה מקסימלית ברשת הזרימה המתוארת.
  • אם ערך הזרימה הוא NN החזר את השיבוץ כמתואר, אחרת בטל את החתונה.

נכונות: מהטענות לעיל.

סיבוכיות: הפעולה היקרה היא מציאת זרימה ברשת המתוארת ואותה ניתן למצוא ב-O(nmN)O(nmN).

2

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

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

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

  • בסיס: בתחילת האלגוריתם הטענה נכונה.
  • צעד: אם בצעד ה-ii הטענה נכונה אז נשים לב שבצעד ה-i+1i + 1 מתחילים לשבץ את האנשים מהשולחנות הכי פנויים ולא משבצים יותר מאיש אחד לאותו שולחן ולכן הטענה נכונה גם אחרי הצעד ה-i+1i + 1

נכונות: מהטענה נובע כי אם קיים שיבוץ חוקי אז ניתן לשבץ את כל המשפחות.

הוכחה: נניח בשלילה שלא, ונסמן ב-flf_l את המשפחה הראשונה שלא ניתן לשבץ, אם לא ניתן לשבץ אותה אז מספר השולחנות שנותרו פנויים קטן מ-nln_l אבל זה גורר שסך המקומות הפנויים קטן מ-nln_l

  • סתירה.

סיבוכיות: O(ni)O(\sum n_i).

1
Feedback