דף זו הוא הראשון משלשה העוסק באלגוריתמים למציאת זרימת המקסימום בגרף מכוון המתאר "רשת צינורות".
כדאי לדעת:
נחלק את החומר שנלמד בזרימה לשלשה חלקים:
כדאי לדעת:
בספר הקורס , הפרק "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].
