Question

matching
winter_15-16_a

נתונות שתי חלוקות של [n][n] ל-kk קבוצות זרות, A1,,AkA_1, \ldots, A_k ו-B1,,BkB_1, \ldots, B_k בהתאמה. כלומר לכל שני אינדקסים 1i<jk1 \leq i < j \leq k מתקיים כי: AiAj=BiBj=A_i \cap A_j = B_i \cap B_j = \emptyset, וכמו כן מתקיים כי i=1kAi=i=1kBi=[n]\bigcup_{i = 1}^k A_i = \bigcup_{i = 1}^k B_i = [n].

קבוצה S[n]S \subseteq [n] בגודל kk הנחתכת עם כל אחת מ-2k2k הקבוצות A1,,Ak,B1,,BkA_1, \ldots, A_k, B_1, \ldots, B_k תקרא מועצה. שימו לב שמועצה לא בהכרח קיימת.

א. הוכיחו כי אם קיימת מועצה SS, אז בהכרח במועצה זו איבר אחד בדיוק מכל אחת מהקבוצות A1,,Ak,B1,,BkA_1, \ldots, A_k, B_1, \ldots, B_k.

ב. הציעו אלגוריתם המכריע אם קיימת מועצה, ואם היא קיימת גם מחשב אותה בסיבוכיות זמן O(nk)O(nk) (הניחו שלכל מספר i[n]i \in [n] נתון לאילו קבוצות הוא שייך).

1

Answers

א. נניח בשלילה ובלי הגבלת הכלליות שב-SS שני איברים מ-A1A_1, מכיוון ש-SS מועצה ו-A1,,AkA_1, \ldots, A_k קבוצות זרות אז ב-SS קיימים לפחות עוד k1k - 1 איברים ולכן SS בגודל k+1k + 1 לפחות - סתירה.

ב. נראה שהבעיה שקולה למציאת שידוך מושלם בגרף הדו צדדי (לא בהכרח פשוט) הבא:

G=({A1,,Ak}{B1,,Bk},E)G = (\{A_1, \ldots, A_k\} \cup \{B_1, \ldots, B_k\}, E)

כאשר

E={ei=(Aj,Bj):i[n],iAjBj}E = \{e_i = (A_j, B_{j'}): i \in [n], i \in A_j \cap B_{j'}\}

נניח שקיימת מועצה S[n]S \subseteq [n] נשים לב ש-{ei:iS}\{e_i : i \in S\} שידוך מושלם (בגודל kk ולפי סעיף א' אין שתי קשתות שנוגעות באותו צומת).

מצד שני, אם MEM \subseteq E שידוך מושלם, אז {i:eiM}\{i : e_i \in M\} מועצה (קבוצה בגודל kk, ולפי בניית הגרף לכל קבוצה Ai,BjA_i, B_j קיים נציג ב-SS).

אלגוריתם:

  • בנה את הגרף המתאים
  • מצא שידוך מושלם, אם לא קיים הודע שלא קיימת מועצה, אחרת החזר את המועצה המתאימה.

נכונות: על פי האבחנות לעיל.

סיבוכיות: בניית הגרף ניתן לעשות בזמן O(n+k)O(n + k) שידוך מושלם ניתן למצוא על ידי אחד מאלגוריתמי זרימת מקסימום בזמן O(nk)O(nk).

1
Feedback