Question

matching

נתונה מטריצה בינרית, AA, בגודל n×nn \times n. קבוצה מנצחת היא פרמוטציה π:[n][n]\pi:[n] \to [n] כך שלכל i[n]i \in [n] מתקיים A[i][π(i)]=1A[i][\pi(i)] = 1. כלומר קבוצה של nn תאים עם ערך 1 כך שמכל שורה ומכל עמודה של המטריצה נבחר תא אחד בדיוק.

הציעו אלגוריתם שמוצא קבוצה מנצחת במטריצה או מודיע שאין כזאת. על האלגוריתם לרוץ בסיבוכיות O(n3)O(n^3).

1

Answers

נראה רדוקציה לשידוך בגרף דו"צ:

G=({r1,,rn}{c1,,cn},E)G = (\{r_1, \ldots, r_n\} \cup \{c_1, \ldots, c_n\}, E)

כאשר

E={ricj:A[i][j]=1}E = \{r_ic_j : A[i][j] = 1\}

טענה: קיימת קבוצה מנצחת אמ"מ קיים שידוך מושלם ב-GG.

הוכחה: נניח ש-MM שידוך מושלם ונגדיר nn תאים {A[i][j]:ricjM}\{A[i][j] : r_ic_j \in M\}. צריך להראות שבקבוצת התאים הנ"ל אין שני תאים באותה שורה ובאותה עמודה וזה נכון כי אם היו אז MM לא היה שידוך.

מצד שני, אם π:[n][n]\pi : [n] \to [n] קבוצה מנצחת נגדיר קבוצה של nn קשתות, M={ricj:π(i)=j}M = \{r_ic_j : \pi(i) = j\}, נשים לב מאופן הבניה של הגרף שזאת אכן קבוצה של קשתות, וכמו כן אין שתי קשתות עם צומת משותף מכיוון ש-π\pi פרמוטציה.

אלגוריתם:

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

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

סיבוכיות: נשים לב שבגרף O(n)O(n) צמתים ו-O(n2)O(n^2) קשתות ולכן הסיבוכיות לבדיקת שידוך מושלם היא O(n3)O(n^3) כנדרש.

1
Feedback