לדלג לתוכן

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

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

זרימה אפשרית ברשת זרימה נתונה

[עריכה]

שאלה

[עריכה]

פרק זה לוקה בחסר. אתם מוזמנים לתרום לוויקיספר ולהשלים אותו. ראו פירוט בדף השיחה.



זרימה אפשרית בגרף נתון.
זרימה אפשרית בגרף נתון.

תשובה

[עריכה]

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


קיום מסלול משפר והגדלת גודל הזרימה

[עריכה]

שאלה

[עריכה]

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


שימו לב:

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

תשובה

[עריכה]

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

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


שימו לב:

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


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

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

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

קשתות משפרות בכוונים שונים

[עריכה]

שאלה

[עריכה]

בגרף שבתרשים הבא, , ‏ , ‏ והמספר בכל קשת מציין את קיבול הקשת.

מה זה פשוט - חבל על הזמן.
מה זה פשוט - חבל על הזמן.
  1. אנא מצא זרימה חוקית כך שברשת השיורית אין קשתות הפונות שמאלה.
  2. אנא מצא זרימה חוקית כך שברשת השיורית יש לפחות קשת אחת הפונה שמאלה.

תשובה

[עריכה]

בתרשים הבא, צד שמאל מראה זרימה ברשת, וצד ימין מראה את הרשת השיורית. ברשת שיורית זו אין קשתות לכוון שמאל.


אין קשתות לשמאל.
אין קשתות לשמאל.


בתרשים הבא, צד שמאל מראה זרימה ברשת, וצד ימין מראה את הרשת השיורית. ברשת שיורית זו אין קשתות לכוון ימין.


אין קשתות לימין.
אין קשתות לימין.


בתרשים הבא, צד שמאל מראה זרימה ברשת, וצד ימין מראה את הרשת השיורית. ברשת שיורית זו יש קשתות הן לכוון שמאל והן לכוון ימין.


יש קשתות לכל הכוונים.
יש קשתות לכל הכוונים.