דף זו הוא הראשון משלשה העוסק באלגוריתמים למציאת זרימת המקסימום בגרף מכוון המתאר "רשת צינורות".
כדאי לדעת:
נחלק את החומר שנלמד בזרימה לשלשה חלקים:
כדאי לדעת:
בספר הקורס , הפרק "Maximum Flow" (תתי פרקים 1 ו2) מכסה נושא זה.
נתונים גרף מכוון
G
=
(
V
,
E
)
{\displaystyle \displaystyle G=(V,E)}
, טבלת קיבולים לקשתות
E
{\displaystyle \displaystyle E}
, צומת מקור
s
∈
V
{\displaystyle \displaystyle s\in V}
כלשהו, וצומת בור
t
∈
V
{\displaystyle \displaystyle t\in V}
כלשהו. בהינתן צומת
v
∈
V
{\displaystyle \displaystyle v\in V}
כלשהו, רוצים לדעת מה זרימת המקסימום מ
s
{\displaystyle \displaystyle s}
ל
t
{\displaystyle \displaystyle t}
.
דוגמה:
בגרף שבתרשים הבא, המספר המצויין על כל קשת הוא קיבולו:
לקשת
(
1
,
2
)
{\displaystyle \displaystyle (1,2)}
קיבול
1
{\displaystyle \displaystyle 1}
. לכן
1
{\displaystyle \displaystyle 1}
יכולה להזרים
1
{\displaystyle \displaystyle 1}
ליטר לשניה בקשת זו.
לקשת
(
2
,
3
)
{\displaystyle \displaystyle (2,3)}
קיבול
10
{\displaystyle \displaystyle 10}
. לכן
2
{\displaystyle \displaystyle 2}
יכולה להזרים
10
{\displaystyle \displaystyle 10}
ליטר לשניה בקשת זו.
אין קשת מ
1
{\displaystyle \displaystyle 1}
ל
7
{\displaystyle \displaystyle 7}
. לכן
1
{\displaystyle \displaystyle 1}
אינה יכולה להזרים ישירות שום נוזל ל
7
{\displaystyle \displaystyle 7}
.נניח צומת מקור
s
=
1
{\displaystyle \displaystyle s=1}
, וצומת בור
t
=
4
{\displaystyle \displaystyle t=4}
.
בעיית הזרימה.
התרשים הבא מראה את זרימת המקסימום: המספר בסוגריים בכל קשת מציין כמה ליטר לשניה מזרימים בה. כך, לדוגמה, בקשת
(
1
,
6
)
{\displaystyle \displaystyle (1,6)}
מזרימים
2
{\displaystyle \displaystyle 2}
ליטר לשניה.
הפתרון האופטימאלי.
סך הזרימה היא
3
{\displaystyle \displaystyle 3}
, כי בכל יחידת זמן מזרימים
3
{\displaystyle \displaystyle 3}
ליטר לשניה מ1 ל
4
{\displaystyle \displaystyle 4}
. אפשר לבדוק שאין אפשרות לעשות יותר מכך.
הגדרות מדוייקות לבעיה [ עריכה ]
רשת זרימה [ עריכה ]
דוגמה:
ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה):
הקיבולים הם:
c
1
,
2
=
1
{\displaystyle \displaystyle c_{1,2}=1}
c
1
,
6
=
20
{\displaystyle \displaystyle c_{1,6}=20}
c
2
,
3
=
10
{\displaystyle \displaystyle c_{2,3}=10}
c
6
,
5
=
34
{\displaystyle \displaystyle c_{6,5}=34}
c
6
,
7
=
1
{\displaystyle \displaystyle c_{6,7}=1}
c
7
,
3
=
3
{\displaystyle \displaystyle c_{7,3}=3}
c
7
,
5
=
4
{\displaystyle \displaystyle c_{7,5}=4}
c
3
,
4
=
3
{\displaystyle \displaystyle c_{3,4}=3}
c
5
,
4
=
1
{\displaystyle \displaystyle c_{5,4}=1}
לכל צירוף אחר של
u
{\displaystyle \displaystyle u}
ו
v
{\displaystyle \displaystyle v}
,
c
u
,
v
=
0
{\displaystyle \displaystyle c_{u,v}=0}
.
צומת המקור הוא
s
=
1
{\displaystyle \displaystyle s=1}
, וצומת הבור הוא
t
=
4
{\displaystyle \displaystyle t=4}
.
זרימה חוקית [ עריכה ]
הגדרה:
ברשת זרימה, זרימה חוקית היא קביעת ערך
f
u
,
v
{\displaystyle \displaystyle f_{u,v}}
לכל שני
צמתים
u
,
v
∈
V
{\displaystyle \displaystyle u,v\in V}
, כך שיתקיימו התנאים הבאים:
(מגבלת הקיבול) הזרימה הישירה בין שני צמתים אינה עולה על הקיבול ביניהם;
∀
u
,
v
∈
V
f
u
,
v
≤
c
u
,
v
{\displaystyle \displaystyle \forall _{u,v\in V}f_{u,v}\leq c_{u,v}}
.
(שימור הזרם) בכל צומת, למעט (אולי) הצמתים
s
{\displaystyle \displaystyle s}
ו
t
{\displaystyle \displaystyle t}
, הצומת אינו אוגר או מייצר זרם;
∀
u
∈
V
∖
{
s
,
t
}
∑
v
∈
V
f
u
,
v
=
0
{\displaystyle \displaystyle \forall _{u\in V\setminus \{s,t\}}\sum _{v\in V}f_{u,v}=0}
.
(סימטריה הפכית) הזרימה הישירה מצומת
u
{\displaystyle \displaystyle u}
לצומת
v
{\displaystyle \displaystyle v}
היא מינוס הזרימה הישירה מצומת
v
{\displaystyle \displaystyle v}
לצומת
u
{\displaystyle \displaystyle u}
;
∀
u
,
v
∈
V
f
u
,
v
=
−
f
v
,
u
{\displaystyle \displaystyle \forall _{u,v\in V}f_{u,v}=-f_{v,u}}
.
כדאי לדעת:
סטודנטים להנדסה יזהו דמיון בין שני החוקים האחרונים לחוקי קירקהוף .
דוגמה:
ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה):
אפשר לוודא שהזרימה הראשונה שראינו (התרשים השני שבדף זה), בה
f
1
,
2
=
1
,
f
1
,
6
=
2
{\displaystyle \displaystyle f_{1,2}=1,f_{1,6}=2}
, וכו', היא אכן זרימה חוקית.
הזרימה בה
f
u
,
v
=
0
{\displaystyle \displaystyle f_{u,v}=0}
, עבור כל שני צמתים
u
,
v
∈
V
{\displaystyle \displaystyle u,v\in V}
- גם היא זרימה חוקית.
דוגמה:
ברשת הזרימה הראשונה שראינו (התרשים הראשון שבדף זה), הזרימה בתרשים הבא אינה חוקית.
זרימה לא חוקית.
בין היתר:
f
1
,
2
=
5000
>
c
1
,
2
=
1
{\displaystyle \displaystyle f_{1,2}=5000>c_{1,2}=1}
, דבר שסותר את מגבלת הקיבול.
f
2
,
1
+
f
2
,
3
=
−
5000
+
10
≠
0
{\displaystyle \displaystyle f_{2,1}+f_{2,3}=-5000+10\neq 0}
, דבר שסותר את שימור הזרם.
גודל הזרימה [ עריכה ]
דוגמה:
בזרימה הראשונה שראינו (התרשים השני שבדף זה), גודל הזרימה הוא
f
1
,
2
+
f
1
,
6
=
1
+
2
=
3
{\displaystyle \displaystyle f_{1,2}+f_{1,6}=1+2=3}
.
כדאי לדעת:
אפשר לחשוב על הגדרות אחרות לגודל הזרימה, כמו סכום הזרימות שנכנסות ל
t
{\displaystyle \displaystyle t}
, לדוגמה. בסוף
נושא זה יהיה עליך לדעת להוכיח שהגדרות אלו שקולות.
לאחר שראינו את ההגדרות המדוייקות לבעיה, ברור מה אנו מנסים לפתור מבחינה מתמטית. עם זאת, בקורס זה אנו לרוב עוסקים באלגוריתמים בעלי קלט ופלט מוגדרים על ידי טיפוסים בפסוודו-קוד. נעסוק בכך כעת.
נניח שקיבולי הקשתות נתונות ע"י טבלת עלויות. באופן דומה למה שראינו במסלולים זולים לכלל הזוגות , לא נניח שמדובר בטבלת ערבול , אלא נניח שCapacities
היא מטריצה שלה כניסה Capacities[u][v]
לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך Nil
, כבטבלת ערבול). הערך Capacities[u][v]
, הנו:
קיבול הקשת מu
לv
, אם יש קשת כזו.
0
{\displaystyle \displaystyle 0}
אם אין קשת כזו.
לשם הנוחות, בשאר החומר בנושא נגדיר
c
u
,
v
=
{\displaystyle \displaystyle c_{u,v}=}
Capacities[u][v]
.
נרצה פלט שמתאר כמה זורם בכל קשת. באופן כללי יש יש יותר מדרך אחת הגיונית לעשות זאת; אנו נבחר בדרך שייתכן שתיראה
שרירותית בתחילה. נניח שהפלט הוא Flows
, שהיא מטריצה שלה כניסה Flows[u][v]
לכל שני צמתים (כלומר, אף פעם לא מוחזר הערך Nil
,
כבטבלת ערבול). הערך Flows[u][v]
מתאר כמה זורם מ
u
{\displaystyle \displaystyle u}
ל
v
{\displaystyle \displaystyle v}
, שהוא, עפ"י ההגדרה, מינוס מה שזורם מ
v
{\displaystyle \displaystyle v}
ל
u
{\displaystyle \displaystyle u}
.
לשם הנוחות, בשאר החומר בנושא נגדיר
f
u
,
v
=
{\displaystyle \displaystyle f_{u,v}=}
Flows[u][v]
.