Question

shortest_path
spring_18_b

נתון גרף מכוון, G=(V,E)G = (V, E). הפיכה של קשת uvEuv \in E משמעותה הסרה של הקשת מ-EE והוספה של הקשת האנטי מקבילה שלה ל-EE, כלומר EE{uv}{vu}E \leftarrow E \setminus \{uv\} \cup \{vu\}.

א. נתון הגרף הבא:

tikz

הפכו 2 קשתות כך שיהיה מסלול מ-ss ל-tt.

ב. הציעו אלגוריתם שבהינתן גרף מכוון, 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}^+. הציעו אלגוריתם שהופך kk קשתות לכל היותר כך שבגרף המתקבל משקל מסלול קל ביותר מ-ss ל-tt הוא קטן ככל האפשר. יש לנתח סיבוכיות אבל אין צורך להוכיח נכונות.

1

Answers

א. הקשתות הכחולות

tikz

ב. נגדיר גרף חדש D=(V,EE)D = (V, E \cup \overline{E}) כאשר E={uv:vuE}\overline{E} = \{uv : vu \in E\}.

נגדיר פונקציית משקל על הקשתות

w(e)={0if  eE1if  eE w(e) = \begin{cases} 0 & \text{if}\;e \in E \\ 1 & \text{if}\;e \in \overline{E} \end{cases}

טענה: אם משקל מסלול קל ביותר מ-ss ל-tt ב-DD הוא kk אז ניתן להפוך kk קשתות ב-GG כך שקיים מסלול מ-ss ל-tt בגרף המתקבל.

הוכחה: המסלול ב-DD מכיל בדיוק kk קשתות מ-E\overline{E}, נסמן את הקבוצה הזאת ב-SS ונשים לב שאם הופכים את kk הקשתות {uv:vuS}\{uv : vu \in S\} אז קיים מסלול ב-GG מ-ss ל-tt וזאת מכיוון שאם ee קשת במסלול קל ביותר ב-DD אז הקשת האנטי-סימטרית שלה לא במסלול אחרת זה לא מסלול קל ביותר.

טענה: אם המספר המינימלי של קשתות שיש להפוך ב-GG על מנת שיהיה מסלול מ-ss ל-tt הוא kk אז קיים מסלול מ-ss ל-tt ב-DD במשקל kk.

הוכחה: נסתכל על המסלול עם הקשתות ההפוכות ב-GG ונשים לב שזהו מסלול ב-DD. מעבר לכך, על פי הגדרה, משקל הקשתות המקוריות ב-DD הוא 0 ומשקל kk הקשתות ההפוכות הוא 1.

אלגוריתם:

  • בנה את הגרף DD
  • מצא מסלול קל ביותר מ-ss ל-tt ב-DD והחזר את משקלו (אם רוצים את קבוצת הקשתות אז מחזירים את הקשתות עם משקל 1 במסלול קל ביותר).

נכונות: נובעת ישירות מהטענות לעיל.

סיבוכיות:

סך הכל O(E+V)O(E + V).

ג. נשכפל את צמתי הגרף המקורי k+1k + 1 פעמים, V0,,VkV_0, \dots, V_k,

נגדירEi={uivi:uvE}E_i = \{u_iv_i : uv \in E\}, ו-Ei={uivi+1:vuE}\overline{E_i} = \{u_iv_{i + 1} : vu \in E\}.

נגדיר גרף חדש D=(i=0kVi,E0EkE0Ek1)D = (\bigcup_{i = 0}^{k} V_i, E_0 \cup \dots \cup E_{k} \cup \overline{E_0} \dots \cup \overline{E_{k - 1}})

בגרף החדש נמצא עץ מסלולים קלים ביותר מ-s0s_0, TT ונחזיר min{d(s,ti)}0ik\min \{d(s,t_i)\}_{0 \le i \le k}.

סיבוכיות: נשים לב שמספר הצמתים והקשתות בגרף החדש הם O(kV)O(kV) ו-O(kE)O(kE) ולכן ניתן למצוא עץ מסלולים קלים ביותר בגרף החדש, למשל על ידי דיקסטרה, בזמן O(kElogV)O(kE \log V).

1
Feedback