Question

shortest_path
matching
spring_18_a

נתון גרף לא מכוון G=(V,E)G = (V, E) וקשיר, פונקציית משקל, w:ERw:E \to \mathbb{R}, ושתי תתי קבוצות זרות של צמתים בגודל kk, U,WVU, W \subseteq V.

רוצים למצוא קבוצה, PP, של kk מסלולים זרים בקצוות מ-UU ל-WW, כלומר, לכל שני מסלולים ב-PP, u1,,utu_1, \ldots, u_t ו-v1,,vlv_1, \ldots, v_l מתקיים ש-u1,v1Uu_1, v_1 \in U, ut,vlWu_t, v_l \in W, u1̸=v1u_1 \neq v_1 ו-ut̸=vlu_t \neq v_l.

הערה: אין אף מגבלה על צמתי הביניים של המסלולים, בפרט יתכנו מסלולים ב-PP עם צמתי ביניים משותפים וצמתי הביניים יכולים להיות ב-UU או WW.

נגדיר את ערך הפתרון להיות משקל המסלול הכבד ביותר מבין kk המסלולים, כלומר: maxpP  w(p)\displaystyle{\max_{p \in P}}\;w(p).

אנו מעוניינים למצוא פתרון עם ערך קטן ככל האפשר.

א. הוצע האלגוריתם החמדן הבא:

  • אתחל PP \leftarrow \emptyset
  • כל עוד P<k|P| < k:
    • יהא p=u,,wp = u, \ldots, w מסלול קל ביותר מבין כל המסלולים מ-UU ל-WW, עדכן:
      • PP{p}P \leftarrow P \cup \{p\}
      • UU{u}U \leftarrow U \setminus \{u\}
      • WW{w}W \leftarrow W \setminus \{w\}
  • החזר את PP.

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

ב. תנאי הכרחי לקיום פתרון עם ערך LL לכל היותר הוא שלכל צומת ב-UU קיים מסלול לצומת ב-WW במשקל לכל היותר LL.

הראו, על ידי דוגמה נגדית, כי התנאי הנ"ל איננו מספיק לקיום פתרון עם ערך LL לכל היותר.

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

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

1

Answers

א. למשל עבור הגרף הבא כאשר UU הצמתים משמאל ו-WW הצמתים מימין:

tikz

האלגוריתם יבחר מסלול מצומת 1 לצומת 3 ומסלול מצומת 2 לצומת 4. ערך הפתרון הוא 3 אבל קיים פתרון עם ערך 2.

ב. למשל עבור הגרף הבא כאשר UU הצמתים משמאל ו-WW הצמתים מימין ועבור L=1L = 1:

tikz

אז לכל צומת ב-UU קיים מסלול במשקל 1 לצומת ב-WW אבל לא קיים פתרון עם ערך 1.

ג. האלגוריתם:

  • נבנה את הגרף הדו צדדי B=(UW,F)B = (U \cup W, F) כאשר יש קשת מצומת ב-UU לצומת ב-WW אמ"מ קיים מסלול בין שני הצמתים ב-GG במשקל קטן או שווה ל-LL.
  • בדוק אם קיים שידוך מושלם ב-BB ואם כן החזר את קבוצת המסלולים המתאימה לקשתות השידוך. אחרת החזר שלא קיים פתרון עם ערך LL.

סיבוכיות: את בניית הגרף ניתן לעשות על ידי חישוב מסלול קל ביותר בין כל צמתי GG בזמן של O(V3)O(V^3). נשים לב שב-BB יש O(V2)O(V^2) קשתות ומציאת שידוך מושלם ניתן לעשות ב-O(V3)O(V^3), ולכן בסך הכל O(V3)O(V^3).

ד. נשים לב שתמיד קיים פתרון שמשתמש אך ורק במסלולים הקלים ביותר בין צמתים ב-UU לצמתים ב-WW ולכן ערך הפתרון האופטימלי הוא משקל אחד המסלולים האלה. האלגוריתם אם כך מבצע חיפוש בינרי על משקלי המסלולים הקלים ביותר ועבור כל ערך מריץ את האלגוריתם מהסעיף הקודם. סיבוכיות האלגוריתם היא O(V3logV)O(V^3 \log V).

1
Feedback