מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/זרימה שיורית וחתכים/תרגילים
זרימה אפשרית ברשת זרימה נתונה
[עריכה]שאלה
[עריכה]פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.
![זרימה אפשרית בגרף נתון.](http://upload.wikimedia.org/wikibooks/he/3/34/Dsa_possible_flow_problem.png)
תשובה
[עריכה]מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/זרימה שיורית וחתכים/תרגילים/זרימה אפשרית בגרף נתון/תשובה
קיום מסלול משפר והגדלת גודל הזרימה
[עריכה]שאלה
[עריכה]נניח שברשת השיורי יש מסלול משפר. אנא הוכח בצורה מדויקת שאפשר להגדיל את הזרימה.
![]() |
שימו לב: שים לב שאתה אכן מוכיח את טענתך. השתמש בהגדרות הזרימה החוקית וגודל הזרימה. |
תשובה
[עריכה]נניח שמצאנו זרימה חוקית כלשהי, המתאימה לכל שני צמתים . נניח גם שברשת השיורית יש מסלול משפר בעל קיבול . נסמן מסלול זה כ. נשים לב ש ו. מכאן נוכל להסיק את הדברים הבאים:
- מספר הקשתות הנכנס ל במסלול זה קטן ב1 ממספר הקשתות היוצאות ממנו.
- מספר הקשתות היוצא מ במסלול זה קטן ב1 ממספר הקשתות הנכנסות אליו.
- לכל צומת אחר המופיע במסלול, מספר הקשתות הנכנס אליו במסלול שווה בדיוק למספר הקשתות היוצא ממנו.
![]() |
שימו לב: ודא שלא הנחת במובלע שכל צומת מופיע בדיוק פעם אחת בדיוק במסלול. זה רק מקרה פרטי (שאמנם מתאים למקרה הכללי המתואר בשלושת הכללים הקודמים). |
נקח את הזרימה החוקית, נזרים עוד יחידות בכל קשת במסלול המשפר, ונראה מה קורה לזרימה.
- לאחר השיפור, הזרימה הישירה בין שני צמתים היא אם אינו שייך למסלול המשפר, ו אם שייך למסלול המשפר. במקרה השני חייב להתקיים , משום שאם לא כן, לא ייתכן שקיבול המסלול היה . לכן בהכרח .
- הסימטריה ההפכית אינה מופרת, משום שבחרנו בפרשנות לפיה אם אנו מזרימים עוד יחידות מ ל, מזרימים פחות יחידות מ ל.
- שימור הזרם אינו מופר. נקח צומת שנמצא על המסלול. לפי טענה 3 למעלה, אם במסלול (עבור כלשהו), אז גם במסלול (עבור כלשהו). אך זה אומר שהזרימה מהצומת החוצה אינה משתנה, כי .
מה קורה לגודל הזרימה? נתבונן ב. עפ"י טענה 1 למעלה, גודל זה גדל ב בדיוק.
קשתות משפרות בכוונים שונים
[עריכה]שאלה
[עריכה]בגרף שבתרשים הבא, , , והמספר בכל קשת מציין את קיבול הקשת.
![מה זה פשוט - חבל על הזמן.](http://upload.wikimedia.org/wikibooks/he/1/1f/Dsa_really_simple_flow_problem.png)
- אנא מצא זרימה חוקית כך שברשת השיורית אין קשתות הפונות שמאלה.
- אנא מצא זרימה חוקית כך שברשת השיורית יש לפחות קשת אחת הפונה שמאלה.
תשובה
[עריכה]בתרשים הבא, צד שמאל מראה זרימה ברשת, וצד ימין מראה את הרשת השיורית. ברשת שיורית זו אין קשתות לכוון שמאל.
![אין קשתות לשמאל.](http://upload.wikimedia.org/wikibooks/he/4/46/Dsa_really_simple_flow_solution_1.png)
בתרשים הבא, צד שמאל מראה זרימה ברשת, וצד ימין מראה את הרשת השיורית. ברשת שיורית זו אין קשתות לכוון ימין.
![אין קשתות לימין.](http://upload.wikimedia.org/wikibooks/he/f/f0/Dsa_really_simple_flow_solution_2.png)
בתרשים הבא, צד שמאל מראה זרימה ברשת, וצד ימין מראה את הרשת השיורית. ברשת שיורית זו יש קשתות הן לכוון שמאל והן לכוון
ימין.
![יש קשתות לכל הכוונים.](http://upload.wikimedia.org/wikibooks/he/c/c5/Dsa_really_simple_flow_solution_3.png)