רשתות זרימה

Question 1

הסבירו מהי רשת זרימה.

Answer 1

Question 2

הגדירו:

זרימה חוקית ברשת.

Answer 2

Question 3

הגדירו:

שטף של זרימה f.

Answer 3

Question 4

תהי רשת זרימה שבה נכנסת כמות זרימה x לבור.

מהו שטף הרשת?

Answer 4

Question 5

הגדירו:

בעיית זרימה.

Answer 5

Question 6

אילו שני אלגוריתמים פותרים בעיות זרימה?

Answer 6

Question 7

מהו זמן הריצה של אלגוריתם פורד-פאלקרסון?

Answer 7

Question 8

מהו זמן הריצה של אלגוריתם אדמונד-קארפ?

Answer 8

Question 9

איך נמצא התאמה מקסימלית בגרף דו צדדי?

Answer 9

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

Question 10

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

Answer 10

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

Question 11

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

איך נמצא את הזרימה המקסימלית בין קבוצת כל המקורות לכל הבורות?

Answer 11

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

Question 12

תהי רשת זרימה.

מה היחס בין קיבול החתכים בזרימה לבין השטף של הרשת?

Answer 12

לכל חתך (S,T) ולכל זרימה חוקית f:

|f| <= c(S,T)

Question 13

Answer 13

Question 14

מהו משפט השטף והחתך?

Answer 14

משפט השטף והחתך:

קיימים זרימה f וחתך (S,T) כך ש:

|f| = c(S,T)

הזרימה המקסימלית שווה לקיבול החתך המינימלי.

Question 15

האם אנו יכולים למצוא חתך מינימלי ברשת זרימה?

Answer 15

כן

Question 16

איך נמצא את דרגת הקשירות של גרף?

Answer 16

Question 17

מה הלקח מבעיית המשקיעים והשחקנים?

Answer 17

אם יש לנו רשת זרימה, ואנחנו מחפשים “רווח מקסימילי” מצורה כלשהי - זה שקול לחיפוש “הפסד מינימלי”. לכן, נגדיר את משקלי הצלעות ברשת כך שההפסדים יהיו משקלי צלעות שהם חתך בגרף. כך, מציאת זרימה מקסימלית = מציאת קיבול חתך מינימילי = מציאת הפסד מינימלי = מציאת רווח מקסימלי.

Question 18

האם הורדת צלע מחתך מינימלי ברשת בהכרח מקטינה את הזרימה המקסימלית ברשת?

Answer 18

כן

Question 19

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

Answer 19

לא!

ייתכנו כמה חתכים מינימליים, ואלו נותרו מינימליים.
(זו הייתה שאלה ממבחן)