מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמי זרימה/תרגילים/מציאת מסלולים זרים/תשובה

א'

נבנה רשת זרימה בה הגרף הוא הגרף המקורי, ולכל קשת יש קיבול 1. נריץ אלגוריתם זרימה המבטיח זרימות שלמות (כמו, לדוגמה, אלגוריתם Edmonds-Karp. קל להראות שבזרימה המירבית, כל קשת תזרים 0 או 1 (יש בדיוק שתי אפשרויות). קל להראות שהקשתות בהן יש זרימה 1 - הן בדיוק הפתרון לבעיה.

ב'

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

דוגמה: בתרשים הבא, החלק העליון מראה צומת $\displaystyle u$ בגרף המקורי. יש שלוש קשתות שנכנסות אליו, ושתי קשתות שיוצאות ממנו. התמרת הצמתים. החלק התחתון מראה את הצומת לאחר ההפרדה. הצומת הופרד לשני צמתים, $\displaystyle u_{in}$ ו$\displaystyle u_{out}$. שלוש הקשתות שנכנסו ל$\displaystyle u$ בגרף המקורי נכנסות כעת ל$\displaystyle u_{in}$; שתי הקשתות שיצאו מ$\displaystyle u$ בגרף המקורי יוצאות כעת מ$\displaystyle u_{out}$. בגרף החדש, נמתחה קשת $\displaystyle e'_{u}$ מ$\displaystyle u_{in}$ ל$\displaystyle u_{out}$.

כעת נקבע קיבולים לקשתות בגרף החדש. עבור כל קשת בגרף המקורי (לדוגמה $\displaystyle e_{2}$), נתן לה קיבול אינסוף. עבור כל קשת חדשה בגרף החדש (לדוגמה, $\displaystyle e'_{u}$), נתן לה קיבול 1.

נמשיך מכאן כבסעיף הקודם.