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

שאלה 2 – מחלוקות וגרפים (עמוד 8) נתון גרף קשיר ולא מכוונן $G = (V, E)$ עם משקלות חיוביות על הקשתות. הגרף עשוי להכיל קשתות מרובות או לולאות עצמיות (אך לא מרובות). נאמר שקשת $e^*$ היא שקלילה אם היא צריכה להופיע בכל עץ פורש מינימלי של $G$. ההוכחה מבססת על חוקי הטריאנגולציה של Prim. מחלוקות סטנדרטיות: - קשת $e = \{u, v\}$ בגרף היא שקלילה אם ורק אם הצלע מהווה גשר בגרף או משקלה נמוך מכל קשת אחרת המחברת את אותו שני קודקודים. הוכח או הפרך: קשת $e$ היא שקלילה אם ורק אם היא הקשת היחידה בחיתוך מינימלי של $G$.

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

פתרון: הטענה נכונה. נוכיח אותה על ידי פירוש הביטוי "הקשת היחידה בחיתוך מינימלי" כקשת שהיא בעלת המשקל המינימלי באופן יחיד ביחס לחיתוך כלשהו. תכונה זו ידועה בשם **תכונת החתך הבטוח**. קשת $e$ נקראת **קשת קלה** ביחס לחיתוך אם משקלה הוא הנמוך ביותר מבין כל הקשתות באותו חיתוך. הטענה היא שקשת $e$ נמצאת בכל עפ"מ אם ורק אם קיים חתך שבו $e$ היא קשת קלה יחידה. נוכיח את שני כיווני הטענה: **כיוון ראשון ($\oldsymbol{\Leftarrow}$):** נניח שקיים חתך $(S, V \setminus S)$ כך שהקשת $e = (u, v)$ היא **הקשת הקלה היחידה** החוצה אותו. כלומר, $u \in S, v \in V \setminus S$ ולכל קשת אחרת $e'=(u', v')$ החוצה את החתך ($u' \in S, v' \in V \setminus S$), מתקיים $w(e) < w(e')$. נרצה להוכיח כי $e$ חייבת להופיע בכל **עץ פורש מינימלי** (עפ"מ) של $G$. נניח בשלילה שקיים עפ"מ $T$ שאינו מכיל את הקשת $e$. מכיוון ש-$T$ הוא עץ פורש, קיים מסלול יחיד $P$ ב-$T$ בין שני צומתי הקצה של $e$, כלומר בין $u$ ל-$v$. מכיוון ש-$u \in S$ ו-$v \in V \setminus S$, המסלול $P$ חייב לחצות את החתך. לכן, קיימת ב-$P$ לפחות קשת אחת $e' = (x, y)$ כך שגם היא חוצה את החתך $(S, V \setminus S)$. כעת, נבנה גרף חדש $T' = (T \setminus \{e'\}) \cup \{e\}$. - $T'$ הוא עץ פורש: הסרת $e'$ מ-$T$ מנתקת אותו לשני רכיבי קשירות. מכיוון ש-$e$ מחברת בין שני רכיבים אלו (כי היא חוצה את החתך כמו $e'$), הוספתה הופכת את $T'$ לעץ קשיר. מספר הקשתות נותר $|V|-1$, ולכן $T'$ הוא עץ פורש. - נשווה את משקלי העצים: $w(T') = w(T) - w(e') + w(e)$. - מההנחה שלנו, $e$ היא הקשת הקלה היחידה בחתך, ולכן $w(e) < w(e')$. - מכאן נובע כי $w(T') < w(T)$. מצאנו עץ פורש $T'$ שמשקלו קטן ממש ממשקלו של $T$. זוהי סתירה להנחה ש-$T$ הוא עץ פורש מינימלי. לכן, ההנחה הראשונית שלנו שגויה, ו-$e$ חייבת להופיע בכל עפ"מ. $\blacksquare$ **כיוון שני ($\oldsymbol{\Rightarrow}$):** נניח שהקשת $e = (u,v)$ מופיעה בכל עפ"מ של $G$. נרצה להוכיח שקיים חתך $(S, V \setminus S)$ שבו $e$ היא הקשת הקלה היחידה. ניקח עפ"מ כלשהו $T$. אנו יודעים כי $e \in T$. אם נסיר את $e$ מ-$T$, העץ יתפרק לשני רכיבי קשירות. נגדיר את **החתך** $(S, V \setminus S)$ על פי רכיבים אלה: $S$ יהיה קבוצת הצמתים באחד הרכיבים (זה המכיל את $u$), ו-$V \setminus S$ יהיה קבוצת הצמתים ברכיב השני (המכיל את $v$). הקשת $e$ חוצה את החתך הזה מעצם הגדרתו. נותר להוכיח שהיא הקשת הקלה היחידה שחוצה אותו. נניח בשלילה שקיימת קשת אחרת $e'=(x, y)$ החוצה את החתך $(S, V \setminus S)$ כך ש-$w(e') \le w(e)$. - נבנה גרף חדש $T' = (T \setminus \{e\}) \cup \{e'\}$. - $T'$ הוא עץ פורש: הסרת $e$ מ-$T$ מנתקת אותו לשני רכיבי קשירות $S$ ו-$V \setminus S$. הקשת $e'$ מחברת צומת מ-$S$ לצומת מ-$V \setminus S$, ולכן היא מאחה את הרכיבים בחזרה לעץ קשיר. מספר הקשתות נותר $|V|-1$, ולכן $T'$ עץ פורש. - נשווה את משקלי העצים: $w(T') = w(T) - w(e) + w(e')$. - מההנחה בשלילה, $w(e') \le w(e)$, ולכן $w(T') \le w(T)$. מכיוון ש-$T$ הוא עפ"מ, משקלו מינימלי. לכן, גם $T'$ חייב להיות עפ"מ. אבל, $T'$ הוא עפ"מ שאינו מכיל את הקשת $e$. זוהי סתירה להנחה ש-$e$ מופיעה **בכל** עפ"מ. לכן, ההנחה בשלילה שגויה. כלומר, לא קיימת קשת $e'$ כזאת. מכאן ש-$e$ היא הקשת הקלה היחידה החוצה את החתך $(S, V \setminus S)$ שהגדרנו. $\blacksquare$