Question

max_flow
spring_18_b

נתונים שני וקטורים מעל Nn\mathbb{N}^n, rr ו-cc. כמו כן נתונה מטריצה בינרית, AA, מגודל n×nn \times n כך שבחלק מהתאים שלה ישנם אפסים.רוצים למלא את התאים הריקים במטריצה ב-0 או 1 כך שלכל 1in1 \leq i \leq n סכום האיברים בשורה ה-ii שווה ל-r[i]r[i] וסכום האיברים בעמודה ה-ii שווה ל-c[i]c[i]. או להודיע שאין כזאת.

א. מלאו את המטריצה הבאה ב-11 או 00, כך שסכום כל שורה וסכום כל עמודה יתאימו לערכים הנקובים בקצה השורה/העמודה.

20101112 \begin{array}{|c|c|c||c|} \hline &&& 2 \\\hline & 0 & & 1 \\\hline && 0 & 1 \\\hline \hline 1 & 1 & 2& \\\hline \end{array}

ב. הציעו אלגוריתם שבהינתן שני וקטורים, rr ו-cc, בגודל nn עם ערכים שלמים אי-שליליים,מוצא מטריצה

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

נתונה מטריצה מגודל n×nn \times n עם ערכים רציונליים כך שסכום הערכים בכל שורה ובכל עמודה הוא שלם. רוצים לעגל את המטריצה על ידי החלפה של כל ערך, xx, ב-x\lceil x \rceil או ב-x\lfloor x \rfloor מבלי לשנות את סכום הערכים באף שורה ובאף עמודה.

עבור מספר שלם, xx, x=x=x\lceil x \rceil = \lfloor x \rfloor = x

לדוגמה, את המטריצה הבאה ניתן לעגל כך:

1.23.42.43.94.02.17.91.60.5142442811 \begin{array}{|c|c|c|} \hline 1.2 & 3.4 & 2.4 \\\hline 3.9 & 4.0 & 2.1 \\\hline 7.9 & 1.6 & 0.5 \\\hline \end{array} \to \begin{array}{|c|c|c|} \hline 1 & 4 & 2 \\\hline 4 & 4 & 2 \\\hline 8 & 1 & 1 \\\hline \end{array}

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

רמז: הראו רדוקציה לסעיף ב.

ד. הוכיחו כי כל מטריצה עם ערכים רציונליים כך שסכום הערכים בכל שורה ובכל עמודה הוא שלם תמידניתנת לעגול על ידי החלפה של כל ערך, xx, ב-x\lceil x \rceil או ב-x\lfloor x \rfloor מבלי לשנות את סכום הערכים באף שורה ובאף עמודה.

1

Answers

א.

011200111001112 \begin{array}{|c|c|c||c|} \hline 0&1&1& 2 \\\hline 0& 0 & 1& 1 \\\hline 1&0& 0 & 1 \\\hline \hline 1 & 1 & 2& \\\hline \end{array}

ב. נגדיר את רשת הזרימה הבאה: N=(G=(V,E),s,t,c)N = (G = (V, E), s, t, c) כאשר:

V={s}{ci}i[n]{rj}j[n]{t}E={sci}i[n]{cirj}i,j[n]{rjt}j[n]c(sci)=c[i],c(rjt)=r[j]c(cirj)={0if  Aij=01otherwise \begin{array}{l} V = \{s\} \cup \{c_i\}_{i \in [n]} \cup \{r_j\}_{j \in [n]} \cup \{t\} \\\\ E = \{sc_i\}_{i \in [n]} \cup \{c_ir_j\}_{i,j \in [n]} \cup \{r_jt\}_{j \in [n]} \\\\ c(sc_i) = c[i], c(r_jt) = r[j] \\\\ c(c_ir_j) = \begin{cases} 0 & \text{if}\; A_{ij} = 0 \\ 1 & \text{otherwise} \end{cases} \end{array}

האלגוריתם:

  • בנה את רשת הזרימה הנ"ל.
  • מצא זרימת מקסימום בשלמים.
  • קבע Aij=f(cirj)A_{ij} = f(c_ir_j) ואם AA לא מקיימת את התנאים החזר שלא קיימת.

סיבוכיות: רשת הזרימה היא בגודל O(n2)O(n^2) וערך זרימת המקסימום הוא O(n2)O(n^2) ולכן ניתן לחשב את זרימת המקסימום בזמן O(n4)O(n^4).

ג. נשים לב שניתן לפרק את המטריצה AA לשתי מטריצות BB ו-CC כך ש-Bij=AijB_{ij} = \lfloor A_{ij} \rfloor ו-Cij=AijBijC_{ij} = A_{ij} - B_{ij}

נסמן ב-DD מטריצה שמתקבלת מהמטריצה CC על ידי החלפת CijC_{ij} ב-Cij\lfloor C_{ij} \rfloor או ב-Cij\lceil C_{ij} \rceil כך שסכום כל שורה וסכום כל עמודה ב-DD שווה לסכום העמודה או השורה המתאימות ב-CC. נשים לב ש-B+DB + D היא המטריצה המבוקשת.

את המטריצה DD ניתן לחשב באמצעות סעיף ב כך ש-c[i]=j[n]Cijc[i] = \sum_{j\in[n]}C_{ij}, r[j]=i[n]Cijr[j] = \sum_{i \in [n]}C_{ij} והתא ijij של מטריצת הקלט הוא 0 אמ"מ Cij=0C_{ij} = 0.

ד. נשים לב שקיים פתרון בסעיף הקודם אמ"מ ערך הזרימה הוא i[n]c[i]=j[n]r[j]\sum_{i \in [n]}c[i] = \sum_{j \in [n]}r[j]. נראה שתמיד קיימת פונקציית זרימה עם ערך כזה: f(sci)=c[i]f(sc_i) = c[i], f(rjt)=r[j]f(r_jt) = r[j] ו-f(cirj)=Cijf(c_ir_j) = C_{ij}.

קל לוודא שזאת אכן פונקציית זרימה ושערכה הוא i[n]c[i]=j[n]r[j]\sum_{i \in [n]}c[i] = \sum_{j \in [n]}r[j].

נובע מכך שקיימת זרימה בשלמים עם ערך כזה ולכן ניתן לעגל את המטריצה כנדרש.

1
Feedback