מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 11/תשובות

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש


1[עריכה]

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

זיהוי מעגלים שליליים[עריכה]

כידוע, אם יש מעגל שלילי בגרף, המושג מסלול זול ביותר איננו כלל מוגדר (אין מסלול סופי שהוא הזול ביותר). בפרט, אלגוריתם Floyd-Warshall לא יחזיר את התשובה הנכונה.

עם זאת, קל לחזור על ההוכחה של אלגוריתם Floyd-Warshall ולהווכח בנכונות הטענה הבאה. אם יש מעגל שלילי, האלגוריתם יחזיר מטריצה שבה יש לפחות מספר שלילי אחד באלכסון המטריצה (מעגל שלילי פירושו שאפשר להגיע מצומת לעצמו במחיר קטן מ0).

מציאת ארביטראז'[עריכה]

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

2[עריכה]

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

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


שימו לב:

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


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

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

מה קורה לגודל הזרימה? נתבונן ב. עפ"י טענה 1 למעלה, גודל זה גדל ב בדיוק.

3[עריכה]

1[עריכה]

התרשים הבא מראה דוגמה נגדית לטענה.

דוגמה נגדית.

בגרף זה כל הקיבולים שלמים (כל אחד מהם הוא 1). הזרימות מתוארות בסוגריים, ולא כולן שלמות. קל לראות שהזרימה מירבית, מפני שגודל הזרימה (שהוא 1) הוא בדיוק גודל קיבול החתך בין 4 ל5.

2[עריכה]

נראה באינדוקציה ששיטת Ford-Fulkerson תזרים יחידות שלמות במקרה זה.


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


(בסיס האינדוקציה) הרשת השיורית היא בתחילה רשת שלמה - קיבולי הקשתות חיוביים, והזרימה היא 0. לכן כל קיבול במסלול משפר הוא שלם. הזרימה המשפרת גם היא תהיה שלמה.

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

מש"ל.PNG

היות שהזרימה היא שלמה, אז כל איטרציה של Ford-Fulkerson תשפר את הזרימה ב1 לפחות. מספר האיטרציות, לכן, חסום.

3[עריכה]

הטענה נכונה, והיא נובעת מהסעיף הקודם.

שיטת Ford-Fulkerson תפעל בזמן סופי במקרה זה, והיא תזרים זרימה שלמה. כשהשיטה עצרה את פעולתה, לא היה מסלול משפר ברשת השיורית. כבר למדנו שנובע מכך שהזרימה היא מירבית.

4[עריכה]

ראשית נתרגם את השאלה לדרישות מדויקות מעט יותר. השאלה, למעשה, מבקשת לבדוק האם קיימת זרימה ברשת כך שיתקיימו הדברים הבאים:

  1. הזרימה היוצאת מ היא .
  2. מתקיימות הווריאציות הבאות של זרימה חוקית:
    1. (מגבלת הקיבול) הזרימה הישירה בין שני צמתים אינה עולה על הקיבול ביניהם; .
    2. (סימטריה הפכית) הזרימה הישירה מצומת לצומת היא מינוס הזרימה הישירה מצומת

לצומת ;‏ .

    1. (שימור הזרם) בכל צומת, למעט (אולי) הצמתים ו, הצומת אינו אוגר או מייצר זרם; .(שים לב שרק הדרישה השלישית השתנתה.)

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

גרף הפתרון.

בגרף החדש, כל קשת מהצורה בעלת הקיבול , וכל קשת מהצורה בעלת הקיבול .

נבדוק בגרף החדש האם יש זרימה מלבגודל .



משפט:

יש פתרון לבעיה החדשה \Leftrightarrow יש פתרון לבעיה המקורית.



הוכחה: (⇐) נניח שיש פתרון לבעיה החדשה (כלומר, אכן יש זרימה שגודלה ). נתבונן בחתך הבא:

חתך בפתרון.

מה נוכל לראות מחתך זה וממגבלות הזרימה? מצד אחד, גודל הזרימה כאן הוא

מש"ל.PNG

מצד שני, מגבלת קיבול החתך על זרימת החתך אומרת כי

מכאן קל לראות שבהכרח, לכל ,

5[עריכה]

ראשית נבנה את רשת הזרימה המתוארת בתרשים הבא. בגרף זה צמתים:

  1. צמתים , אחד לכל סטודנט
  2. צמתים , אחד לכל חברה
  3. צומת מקור וצומת בור

נגדיר כ את Length(W).

בגרף יש קשתות:

  1. קשת אחת לכל איבר בW בעלת קיבול 1
  2. קשת מ לכל בעלת קיבול 1
  3. קשת מכל ל בעלת קיבול
.

כעת נריץ את אלגוריתם Ford-Fulkerson. נחזיר כתשובה כל זוג שעבורו קיבלנו .



משפט:

האלגוריתם מחזיר תשובה נכונה.



הוכחה: אנו יודעים שאלגוריתם Ford-Fulkerson משפר תמיד בגדלים שלמים (שהרי הקיבולים שלמים). קל מאד להוכיח (פורמלית, באינדוקציה), שבמקרה זה, חלק מהקשתות מ ל יזרימו 1, והשאר 0 (אלו האפשרויות היחידות). נצייר את הגרף המתקבל ממחיקת הקשתות שאינן מזרימות כלום:

.

נניח שיש קשת בין ל. בהכרח הקשת מזרימה 1. מצד שני, הקשת המזרימה מ ל מזרימה גם היא 1. משימור הזרם נובע אם כן שאין קשת אחרת היוצאת מ.טענה כמעט זהה מראה שאין קשת אחרת הנכנסת ל. ברור גם שקשת זו היתה שייכת לגרף המקורי. מכאן נובע שהמערך המוחזר W' אכן משייך אחת לאחת סטודנט לחברה, ואינו ממציא שיוכים שלא הופיעו במקור. קל גם לראות שכל חברה אינה מעסיקה יותר סטודנטים מיכולתה. קל לראות שאם יש התאמה גדולה יותר, אז אפשר להגיע לזרימה גדולה יותר מהמושגת כאן, וזאת בסתירה לנכונות Ford-Fulkerson.

מש"ל.PNG



משפט:

סיבוכיות האלגוריתם .



הוכחה: אם משתמשים ברשימת שכנויות, אז בניית הגרף החדש היא .כבר ראינו בניתוח אלגוריתם Ford-Fulkerson, שסיבוכיותו לינארית במספר הקשתות כפול גודל הזרימה המירבית. מספר הקשתות כאן הוא , והזרימה המירבית היא

מש"ל.PNG