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

נתון גרף מכוון $G = (V,E)$, ותנונות שתי קבוצות של קדקודים זרות $A, B \subseteq V$. קבוצה של צלעות $D \subseteq E$ תקרא **"קבוצה מפרידה"** אם הסרתה מהגרף תנתק את $A$ מ-$B$ (כלומר, בגרף $G' = (V, E \setminus D)$ לא נותר אף מסלול שמתחיל בקדקוד של $A$ ומסתיים בקדקוד של $B$). **קבוצה מפרידה מזערית** הינה קבוצה מפרידה בעלת גודל $|D|$ מזערי. קבוצה של צלעות $C \subseteq E$ תקרא **"קבוצת חתך"** אם ישנה קבוצת קדקודים $\emptyset \neq S \subseteq V$ כך ש-$C$ זהה לקבוצת כל הצלעות שיוצאות מ-$S$ (כלומר $C = \{(x,y) \in E \mid x \in S, y \notin S\}$). הוכיחו/הפריכו כל אחת מהטענות הבאות (טענה א' 11 נק', טענה ב' 22 נק'): טענה א': "כל קבוצה מפרידה הינה קבוצת חתך." טענה ב': "כל קבוצה מפרידה מזערית הינה קבוצת חתך."

רמז: לטענה א' — בנה גרף פשוט ש"מסלול" מ-$A$ ל-$B$ הוא שרשרת של שתי צלעות; הסרת שתיהן מפרידה אך לא מגדירה חתך. לטענה ב' — הגדר $S$ = קבוצת הקדקודים הנגישים מ-$A$ לאחר הסרת $D$; השתמש במזעריות $D$ להוכחה ש-$D = \mathrm{cut}(S)$ בדיוק.

פתרון: **טענה א' — שקרית (דוגמה נגדית):** נגדיר $G = (\{s, u, t\},\ \{(s,u),(u,t)\})$, $A = \{s\}$, $B = \{t\}$. קבוצה $D = \{(s,u),(u,t)\}$ היא מפרידה: לאחר הסרתה הגרף הופך ריק ואין מסלול מ-$A$ ל-$B$. ✓ נבדוק אם $D$ היא קבוצת חתך: נדרש $S$ כך ש-$D = \{(x,y) \in E \mid x \in S, y \notin S\}$. - הצלע $(s,u) \in D$ דורשת $s \in S,\ u \notin S$. - הצלע $(u,t) \in D$ דורשת $u \in S,\ t \notin S$. - אך אי-אפשר ש-$u \in S$ ו-$u \notin S$ בו-זמנית — סתירה! לכן $D$ אינה קבוצת חתך, והטענה **שקרית**. $\blacksquare$ --- **טענה ב' — נכונה:** **הוכחה:** תהי $D$ קבוצה מפרידה **מזערית** מ-$A$ ל-$B$. נגדיר: $$S = \{v \in V \mid \text{קיים מסלול מקדקוד כלשהו ב-}A\text{ ל-}v\text{ בגרף }(V, E \setminus D)\}$$ $A \subseteq S$ (כל קדקוד נגיש מעצמו), ו-$B \cap S = \emptyset$ (כי $D$ מפרידה). בפרט $S \neq \emptyset$. **נוכיח $D = \mathrm{cut}(S) := \{(u,v) \in E \mid u \in S,\ v \notin S\}$:** $(D \subseteq \mathrm{cut}(S))$: תהי $e = (u,v) \in D$. - אם $u \notin S$: אין מסלול מ-$A$ ל-$u$ ב-$G \setminus D$, לכן $e$ אינה על שום מסלול מ-$A$ ל-$B$ — ניתן להוציאה מ-$D$ ועדיין לקבל קבוצה מפרידה, בסתירה למזעריות $D$. - אם $v \in S$: $v$ נגיש מ-$A$ ב-$G \setminus D$ גם ללא $e$, לכן $e$ מיותרת — שוב סתירה למזעריות. לכן $u \in S$ ו-$v \notin S$, כלומר $e \in \mathrm{cut}(S)$. $(\mathrm{cut}(S) \subseteq D)$: תהי $e = (u,v) \notin D$ עם $u \in S$. אזי $e \in E \setminus D$ ו-$u$ נגיש מ-$A$, לכן גם $v$ נגיש — כלומר $v \in S$. לפיכך אין צלע מ-$S$ ל-$V \setminus S$ מחוץ ל-$D$, ו-$\mathrm{cut}(S) \subseteq D$. מכאן $D = \mathrm{cut}(S)$, ולכן $D$ היא קבוצת חתך. $\blacksquare$