שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2022 - הוכח או הפרך

שאלה 1 – מדעונות (צעויות מנוגדות עם צלעות שיליות) (34 נק׳) בשאלה זו דברים בגרפים מכוונים שאפשר לחזור על צלעות. לכל צלע $e$ יש משקל (או עלות) $w(e)$. נחזור על הסימונים הבאים: - בשאלה 1, דברים בגרפים $(V,E)$ בתחום שלנו הם "מדעונות" $=(v_1,\ldots,v_r)$ שהיא סדרת קדקודים שלכל $1 \leq i \leq k$ קיימת צלע $v_i \to v_{i+1}$ בגרף. - עבור מדעון $\pi=(e_1,\ldots,e_k)$, המשקל שלו הוא $w(\pi) = \sum_{i=1}^{k} w(e_i)$. - "מסלול" (path) הוא מדעון שבו כל קדקוד מופיע לכל היותר פעם אחת. - "מעגל" הוא מסלול שבו הקדקוד הראשון שווה לקדקוד האחרון. - קדקודים בדקדקודים: נקראים "זוגות דקדקודים" אם בשתי הדרכים הם מחוברים בצלע בגרף (כלומר קיימת צלע $s \to t$ וגם צלע $t \to s$). - "צלעה שלילית" (negative edge) היא צלע $e$ עם $w(e) < 0$. - "מעגל שלילי" (negative cycle) הוא מעגל עם משקל שלילי. לכל זה הנתון למעלה, הניח שיש לך גרף מכוון $G = (V, E)$ עם אפשרות של משקלות שליליים. הגדר את הבעיה הבאה: **הגדרה:** בעיית "הנתיב הקצר ביותר עם צלעות שלילית" מוגדרת כך: בהינתן גרף $G$ וקדקודים מקור $s$ ויעד $t$, מצא את המסלול מ-$s$ ל-$t$ עם המשקל הקטן ביותר. אם קיים מעגל שלילי בגרף, אז בעיית זו עלולה להיות חסרת משמעות או להיות לא פתירה בצורה רגילה. (א) נניח שבגרף אין מעגלים שליליים. הוכח או הפרך: אם יש מסלול קצר ביותר מ-$s$ ל-$t$, אז כל תת-מסלול של מסלול קצר ביותר הוא גם מסלול קצר ביותר בין קדקודיו. (ב) עכשיו נניח שבגרף כן יכול להיות מעגלים שליליים. תאר אלגוריתם שקובע האם קיים מעגל שלילי הנגיש מהקדקוד $s$. מהי סיבוכיות הזמן של האלגוריתם שלך?

רמז: סעיף (א): הניחו בשלילה שקיים תת-מסלול שאינו הקצר ביותר, ובנו בעזרתו מסלול חדש וקצר יותר בין נקודות ההתחלה והסוף המקוריות. סעיף (ב): השתמשו באלגוריתם למציאת מסלולים קצרים המבוסס על הרפיות חוזרות, ובדקו מה קורה לאחר $|V|-1$ איטרציות.

פתרון: (א) הטענה נכונה. הוכחה: נוכיח זאת ב**דרך השלילה**. יהי $p$ מסלול קצר ביותר מהקדקוד $s$ לקדקוד $t$. נסמן את המסלול כסדרת קדקודים $p = (v_0, v_1, \ldots, v_k)$, כאשר $v_0 = s$ ו-$v_k = t$. ניקח תת-מסלול כלשהו של $p$, שנסמנו $p_{ij} = (v_i, v_{i+1}, \ldots, v_j)$, כאשר $0 \leq i < j \leq k$. תת-מסלול זה הוא מסלול מהקדקוד $v_i$ לקדקוד $v_j$. נניח בשלילה ש-$p_{ij}$ אינו מסלול קצר ביותר מ-$v_i$ ל-$v_j$. משמעות הדבר היא שקיים מסלול אחר, $q_{ij}$, מ-$v_i$ ל-$v_j$ אשר משקלו קטן יותר, כלומר $w(q_{ij}) < w(p_{ij})$. כעת, נבנה מסלול חדש, $p'$, מ-$s$ ל-$t$ באופן הבא: ניקח את המסלול המקורי $p$, נחליף בו את תת-המסלול $p_{ij}$ במסלול הקצר יותר $q_{ij}$. המסלול החדש יורכב מהחלק של $p$ מ-$s$ ל-$v_i$, אחריו המסלול $q_{ij}$ מ-$v_i$ ל-$v_j$, ואחריו החלק של $p$ מ-$v_j$ ל-$t$. נחשב את משקל המסלול החדש $p'$: $w(p') = w(v_0 \to \ldots \to v_i) + w(q_{ij}) + w(v_j \to \ldots \to v_k)$ לשם השוואה, משקל המסלול המקורי $p$ הוא: $w(p) = w(v_0 \to \ldots \to v_i) + w(p_{ij}) + w(v_j \to \ldots \to v_k)$ מאחר והנחנו כי $w(q_{ij}) < w(p_{ij})$, נובע ישירות כי: $w(p') < w(p)$ זוהי **סתירה** להנחה המקורית ש-$p$ הוא מסלול קצר ביותר מ-$s$ ל-$t$, שכן מצאנו מסלול קצר יותר. לכן, הנחת השלילה שגויה, ובהכרח כל תת-מסלול של מסלול קצר ביותר הוא בעצמו מסלול קצר ביותר בין קדקודיו. $\blacksquare$ (ב) כדי לקבוע האם קיים מעגל שלילי הנגיש מהקדקוד $s$, נשתמש ב**אלגוריתם בלמן-פורד** (Bellman-Ford). האלגוריתם מבוסס על **עקרון ההרפיה** (relaxation) ופועל כך שבגרף עם $|V|$ קדקודים, כל מסלול פשוט (שאינו מכיל מעגלים) מכיל לכל היותר $|V|-1$ צלעות. האלגוריתם מבצע $|V|-1$ איטרציות, ובכל איטרציה הוא עובר על כל הצלעות ומנסה "להרפות" אותן, כלומר לשפר את המרחק המשוער לקדקוד היעד של הצלע. אם לאחר $|V|-1$ איטרציות, באיטרציה ה-$|V|$, עדיין ניתן לבצע הרפיה על צלע כלשהי, הדבר מעיד בהכרח על קיום **מעגל שלילי** הנגיש מ-$s$. **תיאור האלגוריתם:** 1. **אתחול:** ניצור מערך מרחקים $d$ בגודל $|V|$. נאפס את המרחק לקדקוד המקור, $d[s] = 0$, ולכל קדקוד אחר $v \neq s$ נקבע $d[v] = \infty$. 2. **הרפיות:** נבצע את הלולאה הבאה $|V|-1$ פעמים: - עבור כל צלע $(u, v) \in E$ בגרף: - אם $d[u] + w(u,v) < d[v]$, נעדכן את המרחק: $d[v] = d[u] + w(u,v)$. 3. **בדיקת מעגל שלילי:** נבצע איטרציה נוספת, ה-$|V|$, על כל הצלעות: - עבור כל צלע $(u, v) \in E$: - אם $d[u] + w(u,v) < d[v]$, פירוש הדבר שנמצא מעגל שלילי הנגיש מ-$s$. האלגוריתם יחזיר `True` ויעצור. אם הלולאה השלישית מסתיימת מבלי שבוצעה אף הרפיה, סימן שאין מעגלים שליליים הנגישים מ-$s$, והאלגוריתם יחזיר `False`. **סיבוכיות זמן:** - שלב האתחול לוקח $O(|V|)$. - שלב ההרפיות מורכב מלולאה חיצונית שרצה $|V|-1$ פעמים, ולולאה פנימית שעוברת על כל $|E|$ הצלעות. סיבוכיות שלב זה היא $O(|V| \cdot |E|)$. - שלב בדיקת המעגל השלילי עובר על כל הצלעות פעם אחת, ולכן סיבוכיותו $O(|E|)$. הסיבוכיות הכוללת של האלגוריתם נשלטת על ידי שלב ההרפיות, ולכן היא $O(|V| \cdot |E|)$.