תרגיל

ניתוח אלגוריתם הכיווץ של קרגר

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

מקורות מטלות

הכנה איכותית למבחן ופתרונות קהילתיים — נוי 2025פתרון קהילתיפתרון מטלה 5 - סיבוכיות.pdfAssignment 5הכנה איכותית ופתרון קהילתי — אינו מקור רשמי

מופעים קשורים בבחינות ובמטלות

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

q-6fabaa9e71a7מפעילים את אלגוריתם כיווץ הקשתות שהוצג בהרצאה על גרף G=(V,E) בעל n קודקודים, עד שנותרים בגרף 2 קודקודים. יהא (S, S) חתך מינימלי בגרף G. הוכיחו כי ההסת…0 בחינות · 1 מטלות · שיעורים 4, 5, 6, 7, 12, 13, 14

שאלה

הוכיחו שריצה אחת של אלגוריתם קרגר מחזירה חתך מינימום בהסתברות לפחות $2/(n(n-1))$ . כמה ריצות בלתי־תלויות מספיקות כדי להקטין את הסתברות הכישלון ל- $\delta$ ?

רמז 1

התנו בכך שחתך מינימום קבוע בגודל $\lambda$ שרד עד שנותרו $i$ קודקודי־על.

רמז 2

הדרגה המינימלית היא לפחות $\lambda$ , ולכן יש לפחות $i\lambda/2$ צלעות.

פתרון מלא

כל עוד החתך הקבוע שרד, גודלו נשאר $\lambda$ , וכל קודקוד־על בעל דרגה לפחות $\lambda$ ; אחרת צלעותיו היו חתך קטן יותר. לכן כשנותרו $i$ קודקודי־על יש לפחות $i\lambda/2$ צלעות. לכל היותר $\lambda$ מהן שייכות לחתך, ולכן הסתברות שימורו בצעד הבא היא לפחות $1-2/i$ .

מכפלת ההסתברויות המותנות נותנת

\Pr[\mathrm{survive}] \ge\prod_{i=n}^{3}\frac{i-2}{i} =\frac{2}{n(n-1)}=:p.

אם החתך שרד עד שני קודקודי־על, הוא הפלט. ההסתברות שכל $r$ הריצות הבלתי־תלויות ייכשלו היא לכל היותר $(1-p)^r\le e^{-pr}$ . לכן מספיק

r\ge\frac{\ln(1/\delta)}p =\frac{n(n-1)}2\ln\frac1\delta.

נקודת בדיקה

יש לשמור צלעות מקבילות, משום שהריבוי משפיע על ההתפלגות. אחרי כיווץ מוחקים רק לולאות עצמיות.

הערת מקור

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

טעויות נפוצות

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

מקורות ואימות

Arora-Barak draft, randomized-algorithms discussion
הערת כיסוי הקורפוס: אין כיסוי ישיר בסיכום הממוזג או בתמלילי 2026.
מיפוי קטלוג: data/exercises.json; הניסוח והפתרון עצמאיים; הגשות אישיות אינן מקור סמכות.

חתך קבוע המשמש רק לניתוחקשת בטוחה שמכווצים

פתיחה בגלריית ההמחשות: כיווץ קרגר