18בעיית החתך המינימלי: אלגוריתם הכיווץ האקראי, והשיטה ההסתברותית

בקצרה

• בעיית החתך המינימלי ($\mathrm{MINCUT}$): בהינתן גרף $G=(V,E)$, למצוא $\emptyset \subsetneq S \subsetneq V$ שממזערת את מספר הקשתות בין $S$ ל-$\bar{S}$. זו לא בעיה $\mathrm{NP}$-קשה — אבל האלגוריתם שנלמד כאן מעניין בפשטותו ולא ביעילותו.
• אלגוריתם הכיווץ: כל עוד יש יותר משני קודקודים, בחר קשת אקראית אחידה וכווץ אותה; בסוף החזר את החתך שנוצר. שורה אחת של קוד, וניתוח שלם.
• המשפט המרכזי: לכל גרף קבוע $G$ ולכל חתך מינימלי ספציפי $(S,\bar{S})$, ההסתברות — מעל מטבעות האלגוריתם בלבד — שהאלגוריתם מחזיר בדיוק את $(S,\bar{S})$ היא לפחות $1/\binom{n}{2}$.
• הכלי שמניע את כל הניתוח הוא חסם אחד: בכל גרף, גודל החתך המינימלי מקיים $K \le \frac{2|E|}{|V|}$, וזה נשמר לאורך כל ריצת האלגוריתם.
• הגברה: $\lceil\binom{n}{2}\ln 2\rceil$ הרצות בלתי תלויות והחזרת החתך הקטן ביותר שהתקבל מעלות את הסתברות ההצלחה מעל $\tfrac12$. הטעות כאן חד-כיוונית, ולכן מחזירים מינימום ולא רוב.
• מסקנה קומבינטורית: בכל גרף יש לכל היותר $\binom{|V|}{2}$ חתכים מינימליים — מתוך $2^{|V|-1}-1$ חתכים בסך הכל. טענת ספירה טהורה, שמוכחת בעזרת אלגוריתם אקראי.
• החלק השני — השיטה ההסתברותית: בכל גרף קיימת $U \subseteq V$ שהחתך $(U,\bar{U})$ מכיל לפחות $\frac{|E|}{2}$ קשתות. ההוכחה מגרילה את $U$ במטבעות, מחשבת $\mathbb{E}[X]=\frac{|E|}{2}$ בלינאריות התוחלת, ומסיקה קיום מכך ש-$\Pr[X \ge \mathbb{E}[X]]>0$.
• זו הוכחה שונה לתוצאה שכבר ראינו פעמיים דטרמיניסטית (ראו שיעור 13 ושיעור 14) — וזה בדיוק העניין: טענה קומבינטורית שאין בה שום אקראיות, שמוכחת בכלים הסתברותיים.

רקע ותלויות

משיעור 17 — ההגדרות והאלגוריתם. בסוף שיעור 17 כבר הוצגו בעיית החתך המינימלי, פעולת הכיווץ של קשת ואלגוריתם הכיווץ עצמו, ואף נעשה מעקב אחרי כיווץ אחד על גרף לדוגמה — אבל הניתוח נדחה במפורש לשיעור הזה ([00:00:32]: "הנה האלגוריתם, ראינו אותו בסוף השיעור שעבר"). לכן החלוקה כאן היא: ההגדרות והאלגוריתם מובאים שוב בקצרה כדי שהקובץ יעמוד בפני עצמו (ראו שיעור 17 להצגה הראשונה ולציור), וכל הניתוח — חסם הדרגה, הסתברות ההצלחה, ההגברה וחסם מספר החתכים המינימליים — נכתב כאן במלואו.

מה-$\mathrm{MAXCUT}$ הקודם. בשיעור 10 הוכחנו ש-$\mathrm{MAXCUT}$ היא $\mathrm{NP}$-קשה, ברדוקציה $\mathrm{3NAE} \le_p \mathrm{MAXCUT}$ (התזכורת על הכיוון: $A \le_p B$ פירושו ש-$B$ היא הקשה מבין השתיים, כלומר פתרון יעיל ל-$B$ נותן פתרון יעיל ל-$A$). בשיעור 13 ראינו אלגוריתם חיפוש מקומי שנותן יחס קירוב $\tfrac12$ ל-$\mathrm{MAXCUT}$: מזיזים קודקוד מצד לצד כל עוד זה משפר את החתך; בעצירה מתקיים $\mathrm{cut}(v)\ge\mathrm{other}(v)$ לכל $v$, וספירה כפולה נותנת $|F|\ge\tfrac12|E|$. בשיעור 14 ראינו אלגוריתם חמדן במעבר יחיד שמשיג את אותו יחס. שתי התוצאות האלה נותנות בפרט את הטענה הקיומית "בכל גרף יש חתך בגודל $\ge \frac{|E|}{2}$", ובאופן קונסטרוקטיבי. בשיעור הזה נוכיח את אותה טענה קיומית בדרך שלישית, הסתברותית, ולכן היא נכתבת כאן במלואה ואינה כפילות: כל העניין הוא בשיטת ההוכחה, לא בתוצאה.

מבלוק האקראיות. בשיעור 15 הוגדר מהו אלגוריתם אקראי והודגש ההסכם שילווה אותנו גם כאן: הקלט הוא שרירותי וקבוע, וההסתברות נלקחת אך ורק מעל המטבעות הפנימיים של האלגוריתם. בפרט, כשנכתוב כאן "ההסתברות שהאלגוריתם מחזיר חתך מינימלי", זו הסתברות מעל בחירות הקשתות של האלגוריתם עבור הגרף הקבוע $G$ — ולא הסתברות מעל גרפים אקראיים. אין בשיעור הזה שום התפלגות על קלטים. בשיעור 16 (מכונת טיורינג אקראית, $\mathrm{RP}$, $\mathrm{coRP}$, $\mathrm{BPP}$) ראינו את טכניקת ההגברה: הרצות בלתי תלויות מכפילות את הסתברויות הכישלון, ולכן $t$ הרצות מורידות כישלון $\le p$ ל-$\le p^t$. נשתמש בזה כאן כמעט מילה במילה.

כלי אנליטי אחד. נשתמש שוב ושוב באי-השוויון $1+x \le e^{x}$ לכל $x \in \mathbb{R}$, ובפרט $1-a \le e^{-a}$.

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

הגדרות

הגדרה 1: חתך בגרף וגודלו

יהי $G=(V,E)$ גרף פשוט לא מכוון. לכל $S \subseteq V$, החתך המושרה על ידי $S$ הוא הזוג $(S,\bar{S})$, כאשר $\bar{S}=V \setminus S$. גודל החתך הוא מספר הקשתות שקצה אחד שלהן ב-$S$ והשני ב-$\bar{S}$: $\left|(S,\bar{S})\right| \;=\; \bigl|\{\,e=xy \in E \;:\; |e \cap S| = 1\,\}\bigr|.$

אינטואיציה. מחלקים את הקודקודים לשתי קבוצות ומודדים כמה קשתות "נחתכות". שימו לב ש-$(S,\bar{S})$ ו-$(\bar{S},S)$ הם אותו חתך — הסדר לא משנה.

מופע. בגרף המעגל $1-2-3-4-1$ ו-$S=\{1,2\}$ מתקבל חתך בגודל $2$ (הקשתות $23$ ו-$41$).

אי-מופע (מקרה קצה חשוב). $S=\emptyset$ נותנת חתך בגודל $0$, וכך גם $S=V$. בבעיית המינימום (הגדרה 2) נאסור את שני אלה במפורש, כי אחרת הפתרון טריוויאלי. בטענת המקסימום (משפט 10) לא נאסור אותם, כי שם הם ממילא לא מזיקים.

הגדרה 2: בעיית החתך המינימלי

קלט: גרף $G=(V,E)$. מטרה: למצוא קבוצה $\emptyset \subsetneq S \subsetneq V$ שעבורה החתך $(S,\bar{S})$ הוא בגודל מינימלי מבין כל החתכים הלא-טריוויאליים.

נסמן את הבעיה $\mathrm{MINCUT}$ ואת גודל החתך המינימלי בגרף הנתון ב-$K$.

אינטואיציה. זו בדיוק "אותה בעיה" כמו $\mathrm{MAXCUT}$ אבל עם מינימום במקום מקסימום — ואולם היא לא $\mathrm{NP}$-קשה; ידועים לה אלגוריתמים דטרמיניסטיים פולינומיים. הלקח הזה חוזר בקורס: החלפת max ב-min יכולה לשנות את הבעיה מקצה לקצה.

הערה: בהקלטה [00:00:01] הוסבר במפורש מדוע אוסרים את $S=\emptyset$ ואת $S=V$: אחרת "החתך המינימלי" הוא תמיד $0$ והשאלה מתרוקנת מתוכן.

אפשר להניח ש-$G$ קשיר. אם $G$ אינו קשיר, נריץ $\mathrm{BFS}$ מקודקוד כלשהו בזמן $O(|V|+|E|)$. אם לא הגענו לכל הקודקודים, רכיב הקשירות $C$ שמצאנו מקיים $\emptyset \subsetneq C \subsetneq V$ ואין ממנו אף קשת החוצה, כלומר $(C, V\setminus C)$ הוא חתך בגודל $0$ — וזה בוודאי מינימלי. אחרת הגרף קשיר וממשיכים. לכן מכאן ואילך $G$ קשיר, ובפרט $|E| \ge |V|-1$ ו-$|E| \ge 1$.

הגדרה 3: כיווץ קשת (contraction)

תהי $e = xy \in E$. הכיווץ של $e$ הוא הגרף שמתקבל מ-$G$ על ידי החלפת שני הקודקודים $x,y$ בקודקוד חדש יחיד $z$, כאשר כל קשת שהייתה מחוברת ל-$x$ או ל-$y$ הופכת לקשת המחוברת ל-$z$, וכל שאר הקשתות נשמרות. את הקשת $e$ עצמה (וכל קשת מקבילה לה) מוחקים, שכן היא הופכת ללולאה עצמית.

אינטואיציה ועובדה חשובה. התוצאה היא בדרך כלל מולטי-גרף: אם ל-$x$ ול-$y$ היה שכן משותף $w$, הרי שאחרי הכיווץ יש שתי קשתות מקבילות בין $z$ ל-$w$. זה מכוון, ולא באג: מספר הקשתות המקבילות הוא בדיוק מספר הקשתות המקוריות שיחצו את החתך אם $z$ ו-$w$ יופרדו.

למה מוחקים לולאות. לולאה עצמית לעולם אינה חוצה שום חתך, כי שני קצותיה תמיד באותו צד. מחיקתה אינה משנה אף גודל חתך.

הערה: בהקלטה [00:07:36]–[00:08:08] נשאלה בדיוק השאלה הזו. הובהר שם ששני הדברים לגיטימיים — אפשר גם לשמור את הלולאות — וששמירתן לא הייתה שוברת את הניתוח (היא רק מגדילה את $|E|$ ולכן מקטינה את ההסתברות לבחור קשת חוצה). מוחקים אותן כי כך נקי יותר. כמו כן הודגש שבקורס הזה "גרף" פירושו תמיד גרף פשוט לא מכוון אלא אם נאמר אחרת — הכיווץ הוא היוצא מן הכלל שמייצר מולטי-גרף.

מה באמת קורה מאחורי הקלעים. פורמלית איננו "מוחקים קודקודים": אנחנו מחזיקים חלוקה של $V$ לקבוצות (Union–Find), מתחילים מ-$n$ קבוצות יחידון, וכל איטרציה מאחדת שתי קבוצות. בסוף נשארות בדיוק שתי קבוצות, והן $S$ ו-$\bar{S}$ שהאלגוריתם מחזיר. הציור של "מיזוג קודקודים" נוח יותר להבנה, אבל המימוש הוא איחוד קבוצות ([00:09:13]–[00:10:18]).

הגדרה 4: אלגוריתם הכיווץ האקראי

יהי $G=(V,E)$ גרף (קשיר, לפי ההגדרה 2).

1. כל עוד יש בגרף יותר משני קודקודים:
   1. בחר באקראי, באופן אחיד ובלתי תלוי בבחירות הקודמות, קשת $e = xy \in E$ מבין כל קשתות הגרף הנוכחי;
   2. כווץ את $x$ ו-$y$.
2. החזר את החתך המתקבל (שתי קבוצות הקודקודים שנותרו).

הערה מינוח: האלגוריתם הזה מוכר בספרות כאלגוריתם Karger. השם לא נאמר בשיעור ולא נכתב בסיכום; הוא מובא כאן רק כדי שיהיה אפשר לחפש אותו. האלגוריתם עצמו הוצג לראשונה בסוף שיעור 17; כאן הוא חוזר כדי שהניתוח יעמוד בפני עצמו.

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

הערה על הפלט. אפשר להחזיר את החתך עצמו (שתי קבוצות הקודקודים) או רק את גודלו, לפי הגרסה של בעיית האופטימיזציה שמעניינת אותנו (ראו שיעור 13 לטבלת הכרעה/חיפוש/אופטימיזציה).

הגדרה 5: מרחב הסתברות

מרחב הסתברות הוא זוג $(\Omega, \Pr)$ כאשר:

• $\Omega \ne \emptyset$ היא קבוצה הנקראת מרחב המדגם; כל $\omega \in \Omega$ נקראת נקודת מדגם; כל $A \subseteq \Omega$ נקראת מאורע.
• $\Pr : 2^{\Omega} \to [0,1]$ היא פונקציה המקיימת את שלוש אקסיומות ההסתברות:
  1. $\Pr(\Omega) = 1$;
  2. $\Pr(\emptyset) = 0$;
  3. לכל סדרה $A_1, A_2, \ldots \subseteq \Omega$ של מאורעות זרים בזוגות: $\displaystyle \Pr\Bigl(\bigcup_{n=1}^{\infty} A_n\Bigr) = \sum_{n=1}^{\infty} \Pr(A_n)$.

אינטואיציה. הסימון $2^{\Omega}$ הוא קבוצת כל תת-הקבוצות של $\Omega$ (מה שבתורת הקבוצות סימנתם $P(\Omega)$), לא מספר. ההסתברות מוגדרת על תת-קבוצות של $\Omega$ ורק עליהן — זו נקודה שנצטרך אותה מיד.

מופע. הטלת שתי קוביות הוגנות: $\Omega = \{1,\dots,6\}^2$, $|\Omega|=36$, וכל נקודת מדגם בהסתברות $\tfrac{1}{36}$.

אי-מופע. הקבוצה $\{2,3,\dots,12\}$ של הסכומים האפשריים אינה מרחב המדגם של הניסוי הזה. מרחב המדגם הוא אוסף התוצאות המלאות של הניסוי; הסכום מגיע רק בשלב הבא, כפונקציה (הגדרה 6). זו הייתה נקודה שחזרה בהקלטה כמה פעמים ([01:32:23], [01:34:30]).

הגדרה 6: משתנה מקרי ומשתנה אינדיקטור

יהי $(\Omega,\Pr)$ מרחב הסתברות. משתנה מקרי הוא פונקציה $X : \Omega \to \mathbb{R}$. לכל $A \subseteq \mathbb{R}$ מסמנים $\Pr[X \in A] \;:=\; \Pr\bigl(\{\,\omega \in \Omega \;:\; X(\omega) \in A\,\}\bigr).$

משתנה אינדיקטור הוא משתנה מקרי שתמונתו מוכלת ב-$\{0,1\}$.

אינטואיציה. "אין שום דבר מקרי במשתנה מקרי" — זו פונקציה, ותו לא. האקראיות יושבת ב-$\Omega$ וב-$\Pr$, כלומר בקלט של הפונקציה, לא בפונקציה עצמה. הסימון $\Pr[X \in A]$ הוא קיצור: מאחוריו יש תמיד תת-קבוצה של $\Omega$, כי רק לתת-קבוצות של $\Omega$ יש הסתברות. אין הסתברות מוגדרת על $\mathbb{R}$.

מופע. בהטלת שתי קוביות, $X(a,b)=a+b$ הוא משתנה מקרי, ו-$\mathbb{E}[X]=7$.

עובדה שנשתמש בה. לכל משתנה אינדיקטור $I$: $\;\mathbb{E}[I] = 0\cdot\Pr[I=0] + 1\cdot\Pr[I=1] = \Pr[I=1]$.

הגדרה 7: הסתברות מותנית וכלל השרשרת

לכל שני מאורעות $A,B$ עם $\Pr[B]>0$: $\Pr[A \wedge B] \;=\; \Pr[A \mid B] \cdot \Pr[B].$ בהכללה (באינדוקציה), לכל $m$ מאורעות $E_1,\dots,E_m$ עם $\Pr[E_1 \wedge \cdots \wedge E_{m-1}]>0$: $\Pr\Bigl[\bigwedge_{j=1}^{m} E_j\Bigr] \;=\; \Pr[E_1]\cdot\Pr[E_2 \mid E_1]\cdot\Pr[E_3 \mid E_1 \wedge E_2]\cdots\Pr[E_m \mid E_1 \wedge \cdots \wedge E_{m-1}].$

איך לקרוא את הנוסחה. אל תקראו אותה כ"איך מחשבים הסתברות מותנית". קראו אותה כגשר בין "וגם" לבין מותנה, ולכו בכיוון שנוח לכם. בשיעור הזה נלך מ"וגם" למותנה, כי את המותנות דווקא קל לחשב: ההתניה מספרת לנו בדיוק מה מרחב המדגם הנוכחי, כלומר מתוך אילו קשתות בוחרים ([00:44:20]).

משפטים והוכחות

לאורך כל הסעיף: $G=(V,E)$ גרף קלט קבוע ושרירותי, $n=|V|$, ו-$K$ גודל החתך המינימלי בו. כל ההסתברויות והתוחלות הן מעל המטבעות של האלגוריתם — כלומר מעל בחירות הקשתות האקראיות — עבור אותו גרף קבוע. אין כאן שום התפלגות על גרפים.

משפט 1: הדרגה המינימלית חוסמת את החתך המינימלי

טענה. לכל $v \in V$ מתקיים $\deg_G(v) \ge K$.

הוכחה. יהי $v \in V$. נניח $n \ge 2$, ואז $\{v\}$ ו-$V\setminus\{v\}$ שתיהן לא ריקות, כלומר $(\{v\}, V\setminus\{v\})$ הוא חתך חוקי. גודלו הוא בדיוק $\deg_G(v)$, שכן כל קשת שנוגעת ב-$v$ חוצה אותו וכל קשת שאינה נוגעת ב-$v$ אינה חוצה אותו. מכיוון ש-$K$ הוא המינימום על פני כל החתכים החוקיים, ומינימום של קבוצה קטן־שווה מכל איבר בה, נובע $K \;\le\; \bigl|(\{v\}, V\setminus\{v\})\bigr| \;=\; \deg_G(v). \qquad \blacksquare$

מסקנה. $\displaystyle K \le \frac{2|E|}{|V|}$.

הוכחה. לפי למת לחיצת הידיים, $\displaystyle 2|E| = \sum_{v \in V} \deg_G(v)$. לפי הטענה כל מחובר בסכום הוא לפחות $K$, ויש $|V|$ מחוברים, ולכן $2|E| \ge K \cdot |V|$. חלוקה ב-$|V|>0$ נותנת את הדרוש. $\blacksquare$

הערה: בהקלטה [00:19:32]–[00:21:09] התנהל בדיוק כאן ויכוח, ובצדק: אי-השוויון אינו אומר שכל דרגה קטנה מ-$K$ ואינו אומר שכל הדרגות שוות. הוא אומר דבר אחד: לכל קודקוד יש חתך שגודלו בדיוק הדרגה שלו, ולכן המינימום על פני כל החתכים קטן־שווה מכל אחת מהדרגות. הכיוון הוא מהחתך אל הדרגה, לא להפך.

משפט 2: ההבחנה נשמרת לאורך הריצה

נסמן ב-$G_0=G$ את גרף הקלט, וב-$G_j$ את המולטי-גרף שמתקבל אחרי $j$ איטרציות (עם מחיקת לולאות). נסמן $V_j, E_j$ את קבוצות הקודקודים והקשתות של $G_j$. נקבע מראש חתך מינימלי ספציפי $(S,\bar{S})$ של $G$, בגודל $K$.

טענה. נניח שבאיטרציות $1,\dots,j$ לא נבחרה אף קשת החוצה את $(S,\bar{S})$. אז:

1. $|V_j| = n-j$;
2. החתך $(S,\bar{S})$ "שרד" ב-$G_j$: כל קבוצת קודקודים מכווצת ב-$G_j$ מוכלת כולה ב-$S$ או כולה ב-$\bar{S}$, והחתך המושרה ב-$G_j$ הוא עדיין בגודל $K$;
3. $(S,\bar{S})$ הוא חתך מינימלי גם ב-$G_j$, ולכן $\displaystyle K \le \frac{2|E_j|}{|V_j|} = \frac{2|E_j|}{n-j}$.

הוכחה.

(1) כל איטרציה מאחדת שתי קבוצות לאחת, כלומר מורידה את מספר הקודקודים בדיוק באחד. באינדוקציה, אחרי $j$ איטרציות נותרו $n-j$ קודקודים. (זו גם הסיבה שהלולאה מבצעת בדיוק $n-2$ איטרציות: היא עוצרת כשנשארו $2$.)

(2) באינדוקציה על $j$. בסיס $j=0$: כל קבוצה היא יחידון $\{v\}$ ומוכלת בבירור באחד הצדדים. צעד: אם באיטרציה $j$ כווצה קשת $e=xy$ שאינה חוצה את $(S,\bar{S})$, אז $x$ ו-$y$ באותו צד; לפי הנחת האינדוקציה הקבוצות שלהם מוכלות כל אחת בצד שלה, וזה אותו צד, ולכן גם האיחוד שלהן מוכל באותו צד. גודל החתך אינו משתנה: הקשתות שנמחקו הן בדיוק לולאות, שאינן חוצות; כל קשת חוצה של $G$ עדיין קיימת ב-$G_j$ ועדיין חוצה, כי קצותיה נשארו בצדדים שונים.

(3) זה הצעד היחיד שנאמר בהרצאה בקיצור, והנה הפירוט.

הערה: בהרצאה זה נאמר כ"התכונה נשמרת" ([00:23:17], [00:27:37]); הפירוט כאן.

כל חתך של $G_j$ מגדיר חתך של $G$ באותו גודל בדיוק: אם $(T,\bar{T})$ הוא חתך של $G_j$, נפרוס כל קבוצה מכווצת חזרה לקודקודים המקוריים שלה ונקבל חלוקה של $V$; קשת של $G$ חוצה את החלוקה הזו אם ורק אם הקשת המתאימה לה ב-$G_j$ (או הלולאה שלה) חוצה את $(T,\bar{T})$, ולולאות אף פעם לא חוצות. לכן אוסף גדלי החתכים של $G_j$ מוכל באוסף גדלי החתכים של $G$, ומכאן $\min\text{-cut}(G_j) \;\ge\; \min\text{-cut}(G) \;=\; K.$ מצד שני, לפי (2) החתך $(S,\bar{S})$ עצמו קיים ב-$G_j$ ובגודל $K$, ולכן $\min\text{-cut}(G_j) \le K$. שני האי-שוויונות נותנים $\min\text{-cut}(G_j)=K$. כעת מפעילים את המסקנה של משפט 1 על הגרף $G_j$ — ההוכחה שלה לא השתמשה בכך שהגרף פשוט, אלא רק בכך שלכל קודקוד יש חתך שגודלו דרגתו ובלמת לחיצת הידיים, ושתיהן נכונות גם במולטי-גרף — ומקבלים $K \le \frac{2|E_j|}{|V_j|}$. $\blacksquare$

משפט 3: זמן הריצה

טענה. האלגוריתם רץ בזמן $O(|V|\cdot|E|)$ על גרף קשיר.

הוכחה. מספר האיטרציות הוא בדיוק $n-2 = O(|V|)$ (משפט 2(1)). כל איטרציה עולה $O(|V|+|E|)$: בחירת קשת אקראית אחידה נחשבת כאן פעולה אטומית, וכיווץ פירושו לעבור על כל הקשתות שנגעו ב-$x$ וב-$y$ ולחבר אותן לקודקוד החדש, ולמחוק לולאות — כל אלה מעבר ליניארי אחד על הייצוג. סך הכל $O(|V|\cdot(|V|+|E|))$. מכיוון שהגרף קשיר, $|E| \ge |V|-1$, ולכן $|V|+|E| = O(|E|)$ והחסם הוא $O(|V|\cdot|E|)$. $\blacksquare$

משפט 4: קריטריון ההצלחה

טענה. יהי $(S,\bar{S})$ חתך מינימלי של $G$. האלגוריתם מחזיר בדיוק את $(S,\bar{S})$ אם ורק אם באף איטרציה לא נבחרה קשת החוצה את $(S,\bar{S})$.

הוכחה. ($\Rightarrow$, בשלילה) נניח שבאיזושהי איטרציה נבחרה קשת $e=xy$ עם $x \in S$, $y \in \bar{S}$. הכיווץ מאחד את הקבוצה של $x$ עם הקבוצה של $y$, ומרגע זה ואילך הן לעולם באותה קבוצה, כלומר באותו צד של החתך המוחזר. אבל ב-$(S,\bar{S})$ הם בצדדים שונים, ולכן החתך המוחזר אינו $(S,\bar{S})$.

($\Leftarrow$) נניח שלא נבחרה אף קשת חוצה. לפי משפט 2(2), בסוף הריצה כל אחת משתי הקבוצות שנותרו מוכלת כולה ב-$S$ או כולה ב-$\bar{S}$. שתי הקבוצות זרות ואיחודן $V$. אילו שתיהן היו מוכלות באותו צד, נניח ב-$S$, היה מתקבל $V \subseteq S$ בסתירה ל-$\bar{S} \ne \emptyset$. לכן אחת מוכלת ב-$S$ והשנייה ב-$\bar{S}$, ומכיוון שאיחודן $V=S \cup \bar{S}$ והן זרות, בהכרח הראשונה שווה ל-$S$ והשנייה ל-$\bar{S}$. $\blacksquare$

למה זה חשוב. המשפט הזה מתרגם שאלה על פלט לשאלה על מהלך הריצה, וזו שאלה שאנחנו יודעים לחסום איטרציה אחר איטרציה.

משפט 5: הסתברות ההצלחה

טענה. יהי $G$ גרף קשיר קבוע עם $n=|V| \ge 2$, ויהי $(S,\bar{S})$ חתך מינימלי ספציפי שלו. נסמן ב-$A$ את המאורע שהאלגוריתם מחזיר בדיוק את החתך $(S,\bar{S})$. אז, מעל מטבעות האלגוריתם בלבד, $\Pr[A] \;\ge\; \frac{1}{\binom{n}{2}} \;=\; \frac{2}{n(n-1)}.$

למה דווקא חתך ספציפי. את ההסתברות שהאלגוריתם מחזיר איזשהו חתך מינימלי איננו יודעים לחשב. לכן אנחנו חוסמים מלמטה כמות קטנה יותר — ההסתברות להחזיר חתך מינימלי אחד ומסוים — ומכיוון שהמאורע "החזרנו את $(S,\bar S)$" מוכל במאורע "החזרנו חתך מינימלי כלשהו", החסם עובר ([00:12:57]–[00:13:27]).

הוכחה. לכל $1 \le j \le n-2$ נסמן ב-$E_j$ את המאורע שבאיטרציה ה-$j$ לא נבחרה קשת מתוך החתך $(S,\bar{S})$. לפי משפט 4, המאורע $A$ שקול לכך שכל המאורעות $E_j$ התרחשו, ולכן $\Pr[A] \;=\; \Pr\Bigl[\bigwedge_{j=1}^{n-2} E_j\Bigr].$

למה אי אפשר פשוט להכפיל. המאורעות $E_1,\dots,E_{n-2}$ אינם בלתי תלויים. אמנם המטבעות של האלגוריתם בלתי תלויים זה בזה — בכל איטרציה מגרילים מחדש — אבל מרחב הדגימה של איטרציה $j$, כלומר קבוצת הקשתות שמתוכה בוחרים, תלוי לחלוטין במה שכווץ קודם. זו נקודה שקל מאוד לפספס: "בחירה בלתי תלויה" אינה "מאורעות בלתי תלויים" ([00:32:00]). לכן נשתמש בכלל השרשרת (הגדרה 7): $\Pr\Bigl[\bigwedge_{j=1}^{n-2} E_j\Bigr] \;=\; \Pr[E_1]\cdot\Pr[E_2 \mid E_1]\cdot\Pr[E_3\mid E_1\wedge E_2]\cdots\Pr[E_{n-2}\mid E_1 \wedge \cdots \wedge E_{n-3}].$

האיבר הראשון. באיטרציה הראשונה בוחרים קשת אחידה מתוך $|E|$ הקשתות, ומתוכן בדיוק $K$ חוצות. לכן $\Pr[E_1] \;=\; \frac{|E|-K}{|E|} \;=\; 1-\frac{K}{|E|}.$ לפי המסקנה של משפט 1, $K \le \frac{2|E|}{n}$, ולכן $\frac{K}{|E|} \le \frac{2|E|/n}{|E|} = \frac{2}{n}$, ומכאן $\Pr[E_1] \;\ge\; 1-\frac{2}{n}.$

האיבר הכללי. יהי $2 \le j \le n-2$, ונתון $E_1 \wedge \cdots \wedge E_{j-1}$. תחת ההתניה הזו, הגרף הנוכחי הוא $G_{j-1}$ ולפי משפט 2 הוא מקיים: $|V_{j-1}| = n-(j-1) = n-j+1$, החתך $(S,\bar{S})$ שרד בו בגודל $K$, והוא מינימלי בו, ולכן $K \;\le\; \frac{2|E_{j-1}|}{n-j+1}.$ באיטרציה $j$ בוחרים קשת אחידה מתוך $|E_{j-1}|$ קשתות, ומתוכן בדיוק $K$ חוצות, ולכן $\Pr[E_j \mid E_1 \wedge \cdots \wedge E_{j-1}] \;=\; 1-\frac{K}{|E_{j-1}|} \;\ge\; 1-\frac{2}{n-j+1}.$ שימו לב מדוע ההתניה עוזרת ולא מפריעה: היא בדיוק מה שמבטיח שהחתך עדיין שם ועדיין מינימלי, ולכן שהחסם על $K$ עדיין תקף בגרף הנוכחי ([00:44:20]–[00:45:54]).

המכפלה. נציב: $\Pr\Bigl[\bigwedge_{j=1}^{n-2} E_j\Bigr] \;\ge\; \prod_{j=1}^{n-2}\left(1-\frac{2}{n-j+1}\right) \;=\; \left(1-\frac{2}{n}\right)\left(1-\frac{2}{n-1}\right)\left(1-\frac{2}{n-2}\right)\cdots\left(1-\frac{2}{3}\right).$ נחליף אינדקס: $i = n-j+1$ רץ מ-$n$ (עבור $j=1$) עד $3$ (עבור $j=n-2$), ולכן $\prod_{j=1}^{n-2}\left(1-\frac{2}{n-j+1}\right) \;=\; \prod_{i=3}^{n} \frac{i-2}{i} \;=\; \frac{1 \cdot 2 \cdot 3 \cdots (n-2)}{3 \cdot 4 \cdot 5 \cdots n} \;=\; \frac{(n-2)!}{\,n!/2\,} \;=\; \frac{2}{n(n-1)} \;=\; \frac{1}{\binom{n}{2}}.$ הצמצום הטלסקופי גלוי לעין אם כותבים את הגורמים במפורש: $\frac{n-2}{n}\cdot\frac{n-3}{n-1}\cdot\frac{n-4}{n-2}\cdot\frac{n-5}{n-3}\cdots\frac{2}{4}\cdot\frac{1}{3}$ — כל מונה מצטמצם עם המכנה שני מקומות אחריו, ונשארים המונים $2,1$ מהסוף והמכנים $n,n-1$ מההתחלה. $\blacksquare$

הערה מהשיעור [00:47:28]: המרצה הדגיש שהוא עצמו לעולם אינו זוכר אם האינדקס העליון הוא $n-2$ או $n-1$, ושהשיטה הנכונה היא לבדוק ערכים קטנים: ב-$n=3$ יש איטרציה אחת, ב-$n=4$ שתיים — ומכאן שהמספר הוא $n-2$. שווה לאמץ את זה למבחן.

משפט 6: הגברה

האלגוריתם המוגבר. הרץ את אלגוריתם הכיווץ $t = \bigl\lceil \binom{n}{2}\ln 2 \bigr\rceil$ פעמים, בהרצות בלתי תלויות זו בזו, והחזר את החתך הקטן ביותר שהתקבל.

טענה. נסמן ב-$B$ את המאורע שהאלגוריתם המוגבר מחזיר חתך מינימלי. אז $\Pr[B] \ge \tfrac12$.

הוכחה. נקבע חתך מינימלי ספציפי $(S,\bar{S})$, ונסמן ב-$C$ את המאורע שהרצה בודדת מחזירה חתך מינימלי כלשהו, וב-$A$ (כמו במשפט 5) את המאורע שאותה הרצה מחזירה בדיוק את $(S,\bar{S})$. מתקיים $A \subseteq C$, ולכן לפי מונוטוניות ההסתברות (משפט 8(2)) ולפי משפט 5: $\Pr[C] \;\ge\; \Pr[A] \;\ge\; \frac{1}{\binom{n}{2}}.$ לכן הסתברות הכישלון של הרצה בודדת היא $\Pr[\bar{C}] \le 1-\frac{1}{\binom{n}{2}}$.

האלגוריתם המוגבר נכשל, כלומר $\bar B$ מתרחש, אם ורק אם כל $t$ ההרצות נכשלו, וההרצות בלתי תלויות, ולכן ההסתברויות מוכפלות: $\Pr[\bar{B}] \;\le\; \left(1-\frac{1}{\binom{n}{2}}\right)^{t}.$ נשתמש ב-$1+x \le e^{x}$ עם $x = -1/\binom{n}{2}$: $\left(1-\frac{1}{\binom{n}{2}}\right)^{t} \;\le\; \left(e^{-1/\binom{n}{2}}\right)^{\binom{n}{2}\ln 2} \;=\; e^{-\ln 2} \;=\; \frac{1}{2}.$ לכן הסתברות ההצלחה היא לפחות $\tfrac12$. $\blacksquare$

למה מחזירים מינימום ולא רוב. הטעות של האלגוריתם היא חד-כיוונית: הוא תמיד מחזיר חתך חוקי, וגודלו תמיד $\ge K$. אין מצב שבו הוא מחזיר משהו קטן מדי. לכן ההרצה הטובה ביותר היא פשוט הקטנה ביותר, ואין שום צורך בחציון או ברוב. אילו הטעות הייתה דו-כיוונית — כלומר אילו יכולנו לחזור גם מתחת לערך האמיתי וגם מעליו — היינו נאלצים להסתמך על מדד סטטיסטי כמו חציון, וההגברה הייתה נראית אחרת ([00:54:41]–[00:56:47]). זו בדיוק ההבחנה בין טעות חד-צדדית לדו-צדדית שראינו בשיעורים 15–16.

זמן הריצה של האלגוריתם המוגבר. $O\!\left(\binom{n}{2}\right) = O(n^2)$ הרצות, כל אחת $O(|V|\,|E|)$, כלומר $O(|V|^3 |E|)$ — פולינומי, אבל גרוע יותר מהאלגוריתמים הדטרמיניסטיים הידועים ל-$\mathrm{MINCUT}$. היתרון היחיד, והוא אמיתי, הוא הפשטות ([01:00:57]).

משפט 7: מספר החתכים המינימליים

טענה (קומבינטורית). בכל גרף $G=(V,E)$ יש לכל היותר $\binom{|V|}{2}$ חתכים מינימליים.

מדוע זה מפתיע. מספר החתכים בגרף הוא $2^{|V|-1}-1$: יש $2^{|V|}$ תת-קבוצות, פוסלים את $\emptyset$ ואת $V$, וכל חתך נספר פעמיים (פעם כ-$S$ ופעם כ-$\bar{S}$), כלומר $\frac{2^{|V|}-2}{2}=2^{|V|-1}-1$. מבין המספר האקספוננציאלי הזה, רק כמות ריבועית יכולה להיות מינימלית.

הוכחה. נסמן ב-$\ell$ את מספר החתכים המינימליים ב-$G$, ונסדר אותם באופן שרירותי: $C_1,\dots,C_\ell$. נריץ (בדמיון — זהו כלי הוכחה, לא אלגוריתם שמישהו מריץ) את אלגוריתם הכיווץ הבסיסי פעם אחת, ולכל $1 \le j \le \ell$ נסמן ב-$A_j$ את המאורע שהאלגוריתם החזיר את החתך $C_j$.

המאורעות זרים בזוגות: הרצה אחת של האלגוריתם מחזירה בדיוק חתך אחד, ולכן לא ייתכן ש-$A_i$ ו-$A_j$ יתרחשו יחד עבור $i \ne j$.

כל אחד מהם כבד מספיק: לפי משפט 5, המופעל על החתך המינימלי $C_j$ (המשפט תקף לכל חתך מינימלי, לא רק לאחד מיוחד), מתקיים $\Pr[A_j] \ge \frac{1}{\binom{|V|}{2}}$.

חיבור: ההסתברות היא לכל היותר $1$, ולכן, לפי אדיטיביות סופית (משפט 8(0)) עבור מאורעות זרים בזוגות: $1 \;\ge\; \Pr\Bigl[\bigcup_{j=1}^{\ell} A_j\Bigr] \;=\; \sum_{j=1}^{\ell} \Pr[A_j] \;\ge\; \ell \cdot \frac{1}{\binom{|V|}{2}}.$ העברת אגפים נותנת $\ell \le \binom{|V|}{2}$. $\blacksquare$

הערה [01:04:46]: שימו לב מה קרה כאן. הטענה היא טענה קומבינטורית טהורה — ספירה. אין בה אלגוריתם ואין בה הסתברות. ההוכחה, לעומת זאת, היא אלגוריתמית והסתברותית. זה בדיוק הרעיון שנקרא השיטה ההסתברותית, והוא הנושא של יתר השיעור.

משפט 8: תכונות בסיסיות של מרחב הסתברות

יהי $(\Omega,\Pr)$ מרחב הסתברות.

(0) אדיטיביות סופית. לכל $A_1,\dots,A_n \subseteq \Omega$ זרים בזוגות: $\;\Pr\bigl(\bigcup_{j=1}^{n}A_j\bigr) = \sum_{j=1}^{n}\Pr(A_j)$.

הוכחה. אקסיומה 3 מדברת על סדרה אינסופית, ובידינו סדרה סופית. נשלים אותה בקבוצות ריקות: נגדיר $B_k = \begin{cases} A_k & 1 \le k \le n \\ \emptyset & \text{otherwise} \end{cases}$ הקבוצות $B_1,B_2,\ldots$ זרות בזוגות (הקבוצה הריקה זרה לכל קבוצה, ובפרט לעצמה), ולכן לפי אקסיומה 3 ואקסיומה 2: $\Pr\Bigl(\bigcup_{k=1}^{n}A_k\Bigr) = \Pr\Bigl(\bigcup_{k=1}^{\infty}B_k\Bigr) = \sum_{k=1}^{\infty}\Pr(B_k) = \sum_{k=1}^{n}\Pr(A_k) + \sum_{k>n} 0 = \sum_{k=1}^{n}\Pr(A_k).$ השוויון הראשון תקף כי הוספנו לאיחוד רק קבוצות ריקות. $\blacksquare$

(1) משלים. $\Pr(\bar{A}) = 1 - \Pr(A)$. הוכחה. $A$ ו-$\bar{A}$ זרות ואיחודן $\Omega$, ולכן לפי (0) ואקסיומה 1: $1 = \Pr(\Omega) = \Pr(A \cup \bar{A}) = \Pr(A)+\Pr(\bar{A})$. $\blacksquare$

(2) מונוטוניות. אם $A \subseteq B$ אז $\Pr(A) \le \Pr(B)$. הוכחה. נפרק את $B$ למאורעות זרים: $B = A \cup (B \setminus A)$, ו-$A \cap (B\setminus A)=\emptyset$. לפי (0), $\Pr(B) = \Pr(A) + \Pr(B\setminus A)$. מכיוון ש-$\Pr$ מחזירה ערכים ב-$[0,1]$, בפרט $\Pr(B\setminus A) \ge 0$, ולכן $\Pr(B) \ge \Pr(A)$. שימו לב היכן נדרשה ההנחה $A \subseteq B$: בלעדיה $A \cup (B\setminus A)$ אינו $B$. $\blacksquare$

(3) חסם האיחוד (union bound). $\Pr(A \cup B) \le \Pr(A)+\Pr(B)$. הוכחה. $A \cup B = A \cup (B\setminus A)$, ושתי אלה זרות, ולכן לפי (0): $\Pr(A\cup B) = \Pr(A)+\Pr(B\setminus A)$. אבל $B \setminus A \subseteq B$, ולכן לפי (2) $\Pr(B\setminus A) \le \Pr(B)$, ומכאן $\Pr(A\cup B) \le \Pr(A)+\Pr(B)$. $\blacksquare$

משפט 9: שתי הטענות שמניעות את השיטה ההסתברותית

יהי $(\Omega,\Pr)$ מרחב הסתברות.

(1) יהי $A$ מאורע. אם $\Pr[A] > 0$ אז $A \ne \emptyset$.

הוכחה. בשלילה, אם $A = \emptyset$ אז לפי אקסיומה 2 מתקיים $\Pr[A]=\Pr(\emptyset)=0$, בסתירה. $\blacksquare$

(2) יהי $X$ משתנה מקרי בעל תוחלת סופית. אז $\Pr[X \ge \mathbb{E}[X]] > 0$.

הערה: בהרצה ([01:58:47]) הטענה הזו נלקחה כנתונה — "קיבלתי אותה מהשמיים" — ולא הוכחה. הנה ההוכחה עבור מרחב מדגם סופי, שהוא המקרה היחיד שנשתמש בו.

הוכחה (ל-$\Omega$ סופי). נסמן $\mu = \mathbb{E}[X]$ ונניח בשלילה $\Pr[X \ge \mu] = 0$. אז לפי (1) בכיוון ההפוך — או ישירות מהחישוב שלהלן — לכל $\omega \in \Omega$ עם $\Pr(\{\omega\})>0$ מתקיים $X(\omega) < \mu$. נחשב: $\mu \;=\; \mathbb{E}[X] \;=\; \sum_{\omega \in \Omega} \Pr(\{\omega\}) \cdot X(\omega) \;=\; \sum_{\omega:\ \Pr(\{\omega\})>0} \Pr(\{\omega\}) \cdot X(\omega) \;<\; \sum_{\omega:\ \Pr(\{\omega\})>0} \Pr(\{\omega\}) \cdot \mu \;=\; \mu,$ כאשר האי-שוויון החד תקף מפני שהסכום אינו ריק (סכום ההסתברויות הוא $1>0$), והשוויון האחרון כי $\sum_\omega \Pr(\{\omega\}) = \Pr(\Omega)=1$. קיבלנו $\mu < \mu$ — סתירה. $\blacksquare$

איך משתמשים בשתיהן יחד. אם מצליחים לבנות ניסוי אקראי שבו $\mathbb{E}[X]=c$, אז לפי (2) המאורע $\{\omega : X(\omega) \ge c\}$ הוא בעל הסתברות חיובית, ולפי (1) הוא אינו ריק — כלומר קיים $\omega$ שעליו $X(\omega) \ge c$. זהו כל הרעיון: מסיקים קיום מתוחלת.

משפט 10: בכל גרף קיים חתך בגודל $\ge \frac{|E|}{2}$

טענה. יהי $G=(V,E)$ גרף. קיימת קבוצה $U \subseteq V$ כך שהחתך $(U,\bar{U})$ מכיל לפחות $\frac{|E|}{2}$ קשתות.

הערה על ניסוח. כאן לא דורשים $U \ne \emptyset$; הסיכום מציין במפורש שגם $U=\emptyset$ מותרת. זה חף מבעיות: אם $|E| \ge 1$ אז חתך בגודל $\ge \frac{|E|}{2} > 0$ ממילא אינו טריוויאלי.

הניסוי (וזהו למעשה אלגוריתם אקראי). לכל קודקוד $v \in V$, באופן בלתי תלוי בכל שאר הקודקודים, נטיל מטבע הוגן ונכניס את $v$ לקבוצה $U$ בהסתברות $\tfrac12$.

מה בדיוק המרחב. מרחב המדגם הוא $\Omega = 2^{V} = \{\, U : U \subseteq V \,\},$ כלומר תוצאת הניסוי היא קבוצת קודקודים. שוב: ההסתברות היא מעל המטבעות, עבור הגרף הקבוע $G$; $G$ לא הוגרל.

המשתנים המקריים. נסמן ב-$X$ את גודל החתך: $X : 2^{V} \to \mathbb{R}, \qquad X(U) = \bigl|(U,\bar{U})\bigr| .$ ולכל קשת $e \in E$ נסמן ב-$I_e$ את האינדיקטור לכך ש-$e$ חוצה את החתך: $I_e : 2^{V} \to \mathbb{R}, \qquad I_e(U) = \begin{cases} 1 & |e \cap U| = 1 \\ 0 & \text{otherwise}\end{cases}$ (קשת היא קבוצה בת שני קודקודים, ולכן החיתוך $e \cap U$ מוגדר היטב.)

מהגדרת גודל החתך, כשוויון בין פונקציות: $X \;=\; \sum_{e \in E} I_e .$

חישוב התוחלת. מלינאריות התוחלת, $\mathbb{E}[X] \;=\; \sum_{e \in E} \mathbb{E}[I_e].$ תהי $e = xy \in E$ (ומכיוון ש-$G$ פשוט, $x \ne y$). התוחלת של אינדיקטור היא ההסתברות שהוא $1$: $\mathbb{E}[I_e] \;=\; \Pr[I_e = 1] \;=\; \Pr\bigl[(x \in U \wedge y \notin U) \;\vee\; (x \notin U \wedge y \in U)\bigr].$ שני המאורעות זרים — לא ייתכן ש-$x \in U$ וגם $x \notin U$ — ולכן לפי אדיטיביות סופית (משפט 8(0)): $= \Pr[x \in U \wedge y \notin U] \;+\; \Pr[x \notin U \wedge y \in U].$ כעת, המאורע "$x \in U$" נקבע על ידי המטבע של $x$ בלבד, והמאורע "$y \in U$" על ידי המטבע של $y$ בלבד, ומטבעות של קודקודים שונים בלתי תלויים — כאן, ורק כאן, נכנסת ההנחה על אי-התלות בין הקודקודים. לכן כל אחד מהמחוברים מתפרק למכפלה: $= \Pr[x \in U]\cdot\Pr[y \notin U] \;+\; \Pr[x \notin U]\cdot\Pr[y \in U] \;=\; \frac12\cdot\frac12 + \frac12\cdot\frac12 \;=\; \frac12 .$ כלומר $\Pr[I_e=1]=\tfrac12$ ולכן $\mathbb{E}[I_e]=\tfrac12$ לכל $e$, ומכאן $\mathbb{E}[X] \;=\; \sum_{e \in E} \frac12 \;=\; \frac{|E|}{2}.$

מתוחלת לקיום. לפי משפט 9(2) המופעל על $X$, $\Pr\bigl[X \ge \mathbb{E}[X]\bigr] > 0 ,$ כלומר, בכתיב מפורש של הקבוצה שמאחורי הסימון, $\Pr\left(\left\{\, U \subseteq V \;:\; X(U) \ge \frac{|E|}{2} \,\right\}\right) > 0 .$ שימו לב שהאובייקט שבתוך $\Pr$ הוא באמת תת-קבוצה של $\Omega=2^V$ — אוסף של קבוצות קודקודים — כפי שההגדרה דורשת. לפי משפט 9(1) הקבוצה הזו אינה ריקה, כלומר קיימת $U \subseteq V$ שעבורה $X(U) \ge \frac{|E|}{2}$. מהגדרת $X$, זהו בדיוק חתך שגודלו לפחות $\frac{|E|}{2}$. $\blacksquare$

איפה יושבת האקראיות ([01:53:04], [01:59:21]). ב-$\Pr[I_e=1]$ ההסתברות נלקחת על פני $U$, כי $I_e$ היא פונקציה של $U$ — למרות ש-$U$ לא מופיעה בסימון $\Pr[I_e=1]$. וכן: $\mathbb{E}[X]$ הוא מספר קבוע, אין בו שום אקראיות; האקראיות היא במה שמכניסים ל-$X$. המרצה ציין שכל ההערות האלה לא נכתבות בשום טקסט הסתברותי, ושדווקא בגלל זה קל כל כך להתבלבל.

היחס לשיעורים 13 ו-14. את אותה טענה בדיוק כבר הוכחנו פעמיים באופן דטרמיניסטי וקונסטרוקטיבי — בחיפוש מקומי (שיעור 13) ובאלגוריתם החמדן (שיעור 14). ההוכחה כאן אינה משפרת את התוצאה ואינה מייתרת אותן; היא מדגימה שיטה: כדי להוכיח שקיים אובייקט קומבינטורי טוב, מגדירים התפלגות על האובייקטים ומראים שהתוחלת טובה מספיק. אין כאן שום קשר בין הטענה (קומבינטורית) לבין ההסתברות (כלי ההוכחה בלבד).

דוגמאות ותרגילים מהשיעור

דוגמה 1: מעקב מלא אחרי אלגוריתם הכיווץ

נעבוד עם הגרף $G=(V,E)$: $V=\{1,2,3,4,5\}, \qquad E=\bigl\{\{1,2\},\{1,3\},\{2,3\},\{3,5\},\{2,4\},\{4,5\}\bigr\}, \qquad |E|=6 .$ (מבנית: משולש $1\!-\!2\!-\!3$, ומעגל $2-4-5-3-2$.)

הדרגות: $\deg(1)=2,\ \deg(2)=3,\ \deg(3)=3,\ \deg(4)=2,\ \deg(5)=2$; סכומן $12 = 2|E|$ ✓.

מהו החתך המינימלי? הגרף חסין לניתוק בקשת אחת (אין בו גשר), ולכן $K \ge 2$; והחתך $(\{1\},\{2,3,4,5\})$ הוא בגודל $2$. לכן $K=2$. בדיקת המסקנה של משפט 1: $K=2 \le \frac{2\cdot 6}{5}=2.4$ ✓.

ריצה לדוגמה. יש $n-2=3$ איטרציות.

איטרציה 1: נניח שנבחרה הקשת $\{1,3\}$ (בהסתברות $\tfrac16$). מכווצים ומקבלים את הקודקוד $a=\{1,3\}$. הגרף החדש: קודקודים $a,2,4,5$; קשתות: $a\!-\!2$ פעמיים (מ-$\{1,2\}$ ומ-$\{2,3\}$), $a\!-\!5$ (מ-$\{3,5\}$), $2\!-\!4$, $4\!-\!5$. בסך הכל $|E_1|=5$, $|V_1|=4$. הלולאה שנוצרה מ-$\{1,3\}$ נמחקה. בדיקה: $K=2 \le \frac{2 \cdot 5}{4}=2.5$ ✓.

איטרציה 2: נניח שנבחרה $\{2,4\}$ (בהסתברות $\tfrac15$). מקבלים $b=\{2,4\}$. קודקודים: $a,b,5$; קשתות: $a\!-\!b$ פעמיים, $a\!-\!5$, $b\!-\!5$. $|E_2|=4$, $|V_2|=3$. בדיקה: $2 \le \frac{2\cdot4}{3} \approx 2.67$ ✓.

איטרציה 3: יש ארבע קשתות. אם נבחרת אחת משתי הקשתות $a\!-\!b$ (בהסתברות $\tfrac24=\tfrac12$), מקבלים את שתי הקבוצות $\{1,2,3,4\}$ ו-$\{5\}$, כלומר את החתך $(\{5\},\{1,2,3,4\})$ בגודל 2 — מינימלי, הצלחה. אם נבחרת $a\!-\!5$ מקבלים $(\{1,3,5\},\{2,4\})$ בגודל $3$ — כישלון; ואם נבחרת $b\!-\!5$ מקבלים $(\{2,4,5\},\{1,3\})$ בגודל $3$ — כישלון.

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

דוגמה 2: חישוב מדויק של הסתברות ההצלחה, מול החסם

נחשב, על אותו גרף, את ההסתברות המדויקת שהאלגוריתם מחזיר את החתך המינימלי הספציפי $(\{1\},\{2,3,4,5\})$. הקשתות החוצות אותו הן $\{1,2\}$ ו-$\{1,3\}$, כלומר $K=2$.

לפי משפט 4, ההצלחה שקולה לכך שאף אחת משתי הקשתות האלה לא נבחרה. נעקוב אחרי הספירה:

• איטרציה 1: $6$ קשתות, $2$ אסורות $\Rightarrow$ הסתברות $\tfrac46$.
• איטרציה 2: בכל אחת מארבע האפשרויות הכשרות של איטרציה 1, הגרף הנוכחי מכיל $5$ קשתות ובדיוק $2$ מהן עדיין חוצות את $(\{1\},\cdot)$ (משפט 2 מבטיח שהחתך שרד בגודל $K=2$) $\Rightarrow$ הסתברות $\tfrac35$.
• איטרציה 3: באותו אופן, $4$ קשתות ובדיוק $2$ אסורות $\Rightarrow$ הסתברות $\tfrac24$.

לכן, לפי כלל השרשרת, ההסתברות שהאלגוריתם מחזיר בדיוק את החתך $(\{1\},\{2,3,4,5\})$ היא $\frac{4}{6}\cdot\frac{3}{5}\cdot\frac{2}{4} \;=\; \frac{24}{120} \;=\; \frac{1}{5} \;=\; 0.2 .$

והחסם של משפט 5 נותן $\left(1-\frac25\right)\left(1-\frac24\right)\left(1-\frac23\right) \;=\; \frac35\cdot\frac12\cdot\frac13 \;=\; \frac{1}{10} \;=\; \frac{1}{\binom52} \;=\; 0.1 .$

$0.2 \ge 0.1$ ✓. הפער נובע מכך שבגרף הזה מספר הקשתות יורד מהר מהמקרה הגרוע: החסם התיאורטי מניח $\frac{K}{|E_j|} \le \frac{2}{|V_j|}$, כלומר $\tfrac25,\tfrac24,\tfrac23$, ואילו בפועל קיבלנו $\tfrac26,\tfrac25,\tfrac24$.

דוגמה 3: כמה חתכים מינימליים יש בגרף הזה?

מספר החתכים הכולל: $2^{5-1}-1 = 15$. נעבור עליהם ונמצא שהחתכים בגודל $2$ הם בדיוק ארבעה: $(\{1\},\cdot),\quad (\{4\},\cdot),\quad (\{5\},\cdot),\quad (\{4,5\},\{1,2,3\}).$ (לדוגמה, $(\{2\},\cdot)$ הוא בגודל $3$, וכך גם $(\{1,2\},\{3,4,5\})$ ו-$(\{1,3\},\{2,4,5\})$.)