Question

min_cut
shortest_path
summer_18_b

נתון גרף מכוון, G=(V,E)G = (V, E).

א. סמנו 2 קשתות שיש להסיר מהגרף הבא על מנת שלא יהיה בו מסלול מצומת ss לצומת tt.

tikz

ב. הציעו אלגוריתם שבהינתן גרף מכוון, G=(V,E)G = (V, E), וזוג צמתים s,tVs, t \in V מוצא את מספר הקשתות המינימלי שיש להסיר על מנת שלא יהיה מסלול מ-ss ל-tt. יש לנתח סיבוכיות ולהוכיח נכונות.

ג. נתון גרף מכוון, G=(V,E)G = (V, E), זוג צמתים, s,tVs, t \in V, ופונקציית משקל, w:ER+w:E \to \mathbb{R}^+. הציעו אלגוריתם שמוצא את מספר הקשתות המינימלי שיש להסיר כך שבגרף המתקבל משקל מסלול קל ביותר מ-ss ל-tt כבד יותר ממשקל מסלול קל ביותר בגרף המקורי. יש לנתח סיבוכיות אבל אין צורך להוכיח נכונות.

1

Answers

א.

tikz

ב. אלגוריתם:

  • מצא חתך-stst מינימום SS.
  • הסר את כל הקשתות שחוצות את SS.

סיבוכיות:

  • מציאת חתך מינימום ניתן לעשות בזמן O(VE)O(VE) כאשר כל הקיבולים 1.
  • הסרת הקשתות בזמן לינארי.

נכונות: מכיוון שמסירים את כל הקשתות שחוצות את SS אז הצמתים שישיגים מ-ss הם בדיוק SS ו-t/St \notin S.מצד שני, נניח שאת החתך המינימום חוצות kk קשתות וקיימת קבוצה של קשתות, FF כך שב-G=(V,EF)G' = (V, E \setminus F) לא קיים מסלול מ-ss ל-tt. נניח בשלילה ש-F<k|F| < k ונסתכל על קבוצת הצמתים שישיגים מ-ss ב-GG', SS'. נשים לב שהקשתות היחידות שחוצות את SS' ב-GG הן תת קבוצה של FF אז SS' חתך קטן יותר מ-SS - סתירה.

ג. אלגוריתם:

  • מצא את גרף המסלולים הקלים ביותר של GG, H=(V,F)H = (V, F), כאשר F={uv:d(u)=d(v)+w(uv)}F = \{uv : d(u) = d(v) + w(uv)\}.
  • מצא חתך-stst מינימום ב-HH והסר את כל הקשתות שחוצות את החתך.

סיבוכיות:

  • מציאת גרף מסלולים קלים ביותר ניתן לעשות בזמן ElogVE \log V למשל על ידי אלגוריתם דייקסטרה והסרת הקשתות שלא מקיימות את התנאי בזמן לינארי.
  • מציאת חתך מינימום ניתן לעשות בזמן O(VE)O(VE) עבור רשת שכל הקיבולים בה 1.
1
Feedback