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

נתונה נוסחת **3-CNF** $\varphi$ שבה כל אחד מהמשתנים $x_1,\dots,x_n$ מופיע **בדיוק בשלוש** פסוקיות שונות, וכל פסוקית כוללת **בדיוק שלושה** משתנים שונים. הוכיחו כי הנוסחה ספיקה, והציגו אלגוריתם למציאת השמה מספקת. **הדרכה:** היעזרו במשפט Hall.

רמז: ספרו: $3n$ הופעות משתנים $=3m$ משבצות פסוקיות $\Rightarrow n=m$. בנו גרף דו-צדדי פסוקיות–משתנים, והשתמשו במשפט Hall ($3|A|\le 3|\Gamma(A)|$) כדי להסיק קיום זיווג מושלם המשדך לכל פסוקית משתנה שמספק אותה.

פתרון: **מבנה.** מספר הופעות המשתנים הוא $3n$ (כל משתנה ב-3 פסוקיות), והוא שווה למספר משבצות הפסוקיות $3m$ (כל פסוקית 3 משתנים); לכן $n=m$. **גרף דו-צדדי $G$.** צד אחד — קדקוד $u_i$ לכל פסוקית $\varphi_i$; צד שני — קדקוד $v_i$ לכל משתנה $x_i$ (סה"כ $2n$ קדקודים). לכל פסוקית $\varphi_i=(z_{i,1},z_{i,2},z_{i,3})$ נחבר את $u_i$ לשלושת קדקודי המשתנים המופיעים בה. **קיום זיווג מושלם (Hall).** תהי $A$ קבוצת פסוקיות. מספר הצלעות היוצאות מ-$A$ הוא בדיוק $3|A|$, וכל קדקוד-משתנה הוא בעל דרגה $\le 3$ (כל משתנה ב-3 פסוקיות). לכן $3|A|\le 3|\Gamma(A)|$, כלומר $|A|\le|\Gamma(A)|$ — **תנאי Hall מתקיים**, וקיים זיווג מושלם המשדך לכל פסוקית משתנה ייחודי. **מכאן ספיקות.** בזיווג כל פסוקית מותאמת למשתנה שונה המופיע בה. נציב לאותו משתנה את הערך המספק את הליטרל שלו בפסוקית ($T$ אם חיובי, $F$ אם שלילי), ולשאר המשתנים ערך שרירותי. כל פסוקית מסופקת ע"י המשתנה המשודך לה, ואין התנגשות (כל משתנה משודך לכל היותר לפסוקית אחת). לכן $\varphi$ ספיקה. $\blacksquare$ **אלגוריתם למציאת ההשמה.** 0. בנה את $G$ הדו-צדדי; הוסף מקור $s$ המחובר לכל $u_i$ וניקוז $t$ המחובר מכל $v_i$, כל הצלעות בקיבול $1$. 1. הרֵץ אלגוריתם זרימה מקסימלית (Edmonds–Karp); הזרימה המקסימלית (בקיבולים יחידתיים) = זיווג מקסימלי = מושלם. 2. לכל $v_i$ המשודך לפסוקית — הצב את $x_i$ כך שיספק את הליטרל שלו באותה פסוקית; שאר המשתנים כרצוננו. **זמן ריצה.** גרף בעל $2n+2$ קדקודים ו-$O(n)$ צלעות: בנייה $O(n)$, הרצת EK $O(n^2)$ — סה"כ $O(n^2)$.