#algorithms #computer_science

אלגוריתמים ברשתות זרימה

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

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

ניתן להסתכל על כל קשת מכוונת ברשת הזרימה כצינור שהחומר יכול לעבור דרכו , כך שלכל צינור (קשת) יש קיבולת מוגדרת מראש שאומרת מה הקצב המקסימלי שבו החומר יכול לזרום דרך הצינור , למשל 200 וואטס עבור ה״כבל״ $(u, v)$ .

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

רשת זרימה

רשת זרימה היא גרף $G = (V, E)$ מכוון ללא לולאות עצמיות, עם פונקציית קיבול $c : V \times V \to R^{+} \cup {0}$ .
לכל קשת $(u, v) \in E$ מוגדרת קיבולת חיובית $c (u, v) > 0$ ואם זוג קודקודים אינו קשת אז $c (u, v) = 0$ .
נניח שאם $(u, v) \in E$ אז $(v, u) \notin E$ .
נסמן שני קודקודים מיוחדים $s$ קודקוד מקור ו $t$ קודקוד יעד, נניח שהגרף קשיר, כלומר לכל $v \in V$ קיים מסלול ברשת $s \to v \to t$ .

כיוון שלכל קודקוד פרט לקודקודים המיוחדים יש לפחות כניסה אחת ויציאה אחת אז $| E | \geq | V | - 1$ .

Pasted image 20230206161005.png|250
להלן רשת זרימה לדוגמה כאשר המספר על הקשת הוא הקיבולת.

זרימה

ישנן שתי הגדרות שקולות לזרימה.
הגדרה 1
תהי $G = (V, E)$ רשת זרימה עם קיבול $c$ וקודקודי מקור ויעד $s, t$ .
זרימה ב $G$ היא פונקצייה ממשית $f : V \times V \to R$ המקיימת

א) אילוץ הקיבול- לכל זוג קודקודים $u, v \in V$

0 \leq f (u, v) \leq c (u, v)

ב) שימור הזרימה- לכל $v \in V - {s, t}$

\sum_{(u, v) \in E} f (u, v) = \sum_{(v, u) \in E} f (v, u)

ביחס להגדרה זו יתקיים שערך הזרימה הוא

| f | = \sum_{(s, v) \in E} f (s, v) - \sum_{(v, s)} f (v, s)

במקרה שלנו רשתות זרימה לא יכילו קשתות נכנסות ל $s$ ולכן

| f | = \sum_{(s, v) \in E} f (s, v)

מסקנה מיידית מההגדרה:
אם $(u, v) \notin E$ , אין זרימה מ $u$ ל $v$ ולכן $f (u, v) = 0$ .

הגדרה 2
תהי $G = (V, E)$ רשת זרימה עם קיבול $c$ וקודקודי מקור ויעד $s, t$ .
זרימה ב $G$ היא פונקצייה ממשית $f : V \times V \to R$ המקיימת

א) אילוץ הקיבול-

\forall_{u, v \in V} : f (u, v) \leq c (u, v)

ב) סימטריה-

\forall_{u, v \in V} : f (u, v) = - f (v, u)

ג) שימור זרימה- לכל $v \in V - {s, t}$

\sum_{u \in V} f (u, v) = 0

כלומר עבור כל קודקוד שניקח הסכימה של כל הזרימה שנכנסת אליו בכל רגע נתון הוא $0$ .

הערך של זרימה $f$ הוא הזרימה שיוצאת מ $s$ בכל רגע נתון כלומר

| f | = \sum_{v \in V} f (s, v)

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

מסקנה מהגדרה זו:
בניגוד להגדרה הקודמת כאן אם $(u, v) \notin E$ אז $f (u, v) \leq 0$ כלומר הוא יכול להיות שלילי.

דוגמה - עבור רשת הזרימה הבאה עם פונקציית הקיבולת $c$

Pasted image 20230206163000.png|550

זרימה אפשרית תהיה

Pasted image 20230206163027.png|550

זאת אכן זרימה תקנית עבור רשת זרימה תקנית שכן ברור משתי הטבלאות שהחוקים מתקיימים. אפשר לראות גם ששימור הזרימה מתקיים שכן מהטבלה של $f$ אם נסכום כל עמודה נראה שהסכום הוא $0$ .

ערך הזרימה הוא $| f | = 5$ (סכימה של השורה של $s$ בטבלה $f$ ).

זרימת ה0

בדומה למה שעשינו למעלה, ניתן להוכיח גם ש $f = 0$ כלומר פונקציית זרימת ה $0$ היא אכן פונקציית זרימה תקינה לפי ההגדרות

הבחנות

שימור הזרימה אומר שכמות הזרימה שנכנס מהקודקודים ה״רגילים״ צריכה להיות שווה לכמות הזרימה היוצאת מאותם קודקודים , המשמעות של זה היא שנקודות ביניים בדרך ליעד אינן ״אוגרות״ זרימה. הנקודות היחידות שיכולת להוסיף או להפחית זרימה הם $s, t$ . כמו כן ערך הזרימה הוא למעשה כמות הזרימה ש $s$ יוצר בפרק זמן כלשהו.

בפתרון הבעיה אתמקד בהגדרה 2 של זרימה, למרות שהן שקולות אז אין באמת חשיבות באיזה מהם משתמשים

Max Flow

בהינתן רשת זרימה $G = (V, E)$ עם פונקציית קיבול $c$ . נרצה למצוא פונקציית זרימה $f$ עם ערך זרימה מקסימלי $| f |$ .

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

זרימה בין קבוצות:
יהיו $X, Y \subseteq V$ ופונקציית זרימה $f$ אזי

f (X, Y) = \sum_{x \in X} \sum_{y \in Y} f (x, y) = \sum_{(x, y) \in X \times Y} f (x, y)

נשים לב

f ({s}, V) = f (s, V) = \sum_{(s, v) \in {s} \times V} f (s, v) = \sum_{v \in V} f (s, v) = | f |

דוגמה:
עבור רשת הזרימה הקודמת נסמן
$X = {s, v_{1}}, Y = {v_{2}, v_{3}, v_{4}}$

Screenshot 2023-02-06 at 17.13.26.png|250
מתקיים:

f (X, Y) = f (s, v_{3}) + f (v_{1}, v_{3}) + f (v_{1}, v_{2}) = 2 + 2 + 1 = 5

באופן דומה

f (Y, X) = - 2 - 2 - 1 = - 5

טענה
תהי $G = (V, E)$ רשת זרימה עם פונקציית קיבלת $c$ ו $f$ זרימה ברשת. אזי עבור כל $X, Y, Z \subseteq V$ מתקיים:
א) $f (X, X) = 0$
ב) $f (X, Y) = - f (Y, X)$
ג) אם $X \cap Y = \emptyset$ :

f (X \cup Y, Z) = f (X, Z) + f (Y, Z)

f (Z, X \cup Y) = f (Z, X) + f (Z, Y)

הוכחה
א - נובע ישירות מהעובדה שזרימה בין שתי קודקודים היא סימטרית ומהגדרת זרימה על קבוצות אנחנו סוכמים בעצם לכל $f (u, v)$ גם את $f (v, u) = - f (u, v)$ ולכן נקבל ב $0$ .

ב-

f (X, Y) = \sum_{(x, y) \in X \times Y} f (x, y) = \sum_{(x, y) \in X \times Y} - f (y, x) = - \sum_{(y, x) \in Y \times X} f (y, x) = - f (Y, X)

ג-

f (X \cup Y, Z) = \sum_{(m, z) \in X \cup Y, Z} f (m, z) = \sum_{(x, z)} f (x, z) + \sum_{(y, z)} f (y, z) = f (X, Z) + f (Y, Z)

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

f (Z, X \cup Y) = - f (X \cup Y, Z) = - f (X, Z) - f (Y, Z) = f (Z, X) + f (Z, Y)

למה 1
תהי $G = (V, E)$ רשת זרימה ו $f$ זרימה ברשת אזי

| f | = f (V, t)

הוכחה

\begin{matrix} | f | = f (s, V) = f (V, V) - f (V - {s}, V) = - f (V - {s}, V) \\ = f (V, V - {s}) = f (V, V - {s, t}) + f (V, t) \\ = - f (V - {s, t}, V) + f (V, t) \\ = - \sum_{(x, y) \in V - {s, t} \times V} f (x, y) + f (V, t) \\ = \sum_{(y, x) \in V \times V - {s, t}} f (y, x) + f (V, t) \\ = \sum_{y \in V} \sum_{x \in V - {s, t}} f (y, x) + f (V, t) \\ = \sum_{y \in V} 0 + f (V, t) \\ = f (V, t) \end{matrix}

המעבר האחרון נובע מכך שהפעלנו את תכונה שימור הזרימה על כל הקודקודים ובעצם לא סכמנו כלום. המשמעות של זה היא
כמות הזרימה היוצאת מ $s$ בכל רגע נתון שווה לכמות הזרימה שנכנסת ל $t$ בכל רגע נתון שזה מאוד הגיוני בהתחשב בהגדרות שלנו ובעובדה שאמרנו שרק אלו הם הקודקודים שיכולים לאגור או לפזר זרימה וכל האחרים רק מטווחים.

למה 2
תהי $G = (V, E)$ רשת זרימה ותהי $f$ זרימה ברשת.
יהי $(S, V - S)$ חתך של הרשת, כך ש $s \in S$ ו $t \in V - S$ אזי

f (S, V - S) = | f |

הוכחה

\begin{matrix} f (S, V - S) = f (S, V) - f (S, S) = f (S, V) = f (S - {s}, V) + f (s, V) \\ = \sum_{(x, y) \in S - {s} \times V} f (x, y) + f (s, V) \\ = \sum_{x \in S - {s}} \sum_{y \in V} f (x, y) + f (s, V) = \sum_{x \in S - {s}} \sum_{y \in V} - f (y, x) + f (s, V) \\ = 0 + f (s, V) = | f | \end{matrix}

המעבר האחרון נובע משימור זרימה.

דוגמה 1 על אותה זרימה ורשת זרימה שהשתמשנו בה מההתחלה

Pasted image 20230206182607.png|350

\begin{matrix} S = {s, v_{1}, v_{3}} \\ V - S = {v_{2}, v_{4}, t} \\ f (S, V - S) = 2 + 3 = 5 = | f | \end{matrix}

דוגמה 2

Pasted image 20230206182735.png|350

\begin{matrix} S = {s, v_{1}, v_{2}, v_{3}} \\ V - S = {v_{4}, t} \\ f (S, V - S) = 1 + 1 + 3 = 5 = | f | \end{matrix}

שיטת פורד־פולקרסון

נראה עכשיו שיטת FORD-FULKERSON שפותרת את הבעייה של זרימת מקסימום. נשים לב שמדובר ב״שיטה״ ולא באלגוריתם של ממש כי יש כמה מימושים שונים עם זמני ריצה שונים.

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

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

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

Augmenting path - מסלול השיפור

מתחילים עם פונקציית זרימת האפס $f = 0$ ונרצה לעדכן את $f$ כך ש $| f |$ יגדל.
אינטואיטיבית, נמצא מסלול $P$ מ $s$ ל $t$ ונעביר דרכו כמה שיותר זרם.

כמה ניתן להעביר?
ניתן להעביר זרם בידיוק ככמות הקיבולת המינימלית מבין כל הקשתות במסלול, זה כדי לשמור על תנאי אילוץ הקיבול לזרימה!
תהי קשת $(x, y) \in P$ עם הקיבולת המינימלית, לשם הנוחות נגדיר

c f (P) = min (c_{f} (u, v) | (u, v) \in P)

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

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

\forall_{(u, v) \in P} : f (u, v) += c f (P)

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

\forall_{(u, v) \in P} : c (u, v) - = c f (P)

כמו כן צריך לעדכן בהתאם לחוק הסימטריה גם את הזרם והקיבולת בקודקודים $v, u$

\forall_{(u, v) \in P} : f (v, u) - = c f (P), c (u, v) += c f (P)

לאחר התהליך, הקשת $(x, y) \in P$ עם הקיבלות המינימלית תהיה בעלת קיבולת נוכחית $0$ קשת כזאת נקראת ״רוויה״ או Saturated בלעז. כלומר לא ניתן להעביר עוד זרם דרכה.
וכך יכולים לחזור על התהליך עבור כל המסלולים הזרים ולעדכן את הזרימה בהתאם, מסלולים כאלה נקראים Augmenting Paths.

השאלה המתבקשת כעת היא:
מה אם יש מסלול מ $s$ ל $t$ עם קשת שכבר ראינו באחד מהמסלולים הקודמים?
אם נגיע לקשת כזאת והיא רווייה אז היא יכולה לחסום עוד קשתות וכך נפספס מסלולים אפשריים.
כלומר נרצה לייעל את השיטה שלנו לשיטה שבה נוכל להתחרט על העדכון שעשינו, כלומר לחזור דרך הזרם ההופכי (שיהיה שווה למקורי) וכך לחזור צעד אחד אחורה.

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

הרשת השיורית

תהי $G = (V, E)$ רשת זרימה עם פונקציית קיבול $c$ וזרימה $f$ .
הקיבולת השיורית של $c$ ו $f$ מוגדרת להיות $c_{f} = c (u, v) - f (u, v)$ (תמיד אי שלילית)
כלומר ״כמה עוד זרם ניתן להעביר בנוסף לזרם הנוכחי דרך הקשת הזו״.
רשת הזרימה השיורית $G_{f} = (V, E_{f})$ היא רשת זרימה עם פונקציית קיבול $c_{f}$ כאשר

E_{f} = {(u, v) | c_{f} (u, v) > 0}

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

בעצם הרשת השיורית נותנת לנו את היכולת לדעת, כמה הזרמתי לכיוון מסויים על ידי בנייה של קשתות שנכנסות לקשתות שמהן הוצאנו את הזרימה הזאת (יכולות גם להכנס ל $s$ ) אבל הוא גם מראה לנו קשתות שמהן ניתן עוד להזרים מידע ובכך למקסם את הזרם.
הרעיון הוא שעל כל זרימה שנבנה אם קיים מסלול ברשת השיורית מ $s$ ל $t$ אז אני יכול למקסם את הזרימה ברשת המקורית.

למשל אם נסתכל על הרשת זרימה הזאת (כמובן שאמורות להיות גם זרימות שליליות לכיוון השני אבל נזניח את זה לרגע)
IMG_4B5B0E24306E-1.jpeg|250

הרשת השיורית תיראה ככה

IMG_B5BAFA4F7B60-1.jpeg|250

ישנו מסלול $P$ ברשת השיורית מ $s$ ל $t$ ומשמעות הדבר היא שאני יכול עוד למקסם את הזרם, לא בעיה להראות למה זה בא ביחד הרי שאם יש עוד מסלול לאחר העברת הזרם בגרף משמעות הדרך היא שאני יכול לעדכן את הקודקודים הרלוונטים בגרף המקורי ולהוסיף להם את $c_{f} (P)$ של אותו מסלול שיפור ומהגדרת ערך הזרימה היא תגדל גם כן. נשים לב שאנחנו כל הזמן מעדכנים את הזרימה בהתאם למסלול השיפור בפועל מה שיקרה בגרף המקורי הוא שאם הקשת בשיורי נמצאת גם במקורי , נוסיף לה את $c_{f} (P)$ ואחרת אנחנו ״מחזירים״ זרימה שכבר הזרמנו למשל בגרף הנ״ל אנחנו נחזיר זרימה של $1$ כי זה הקיבולת המינימלית במסלול השיפור, במקום להזרים $2$ אנחנו נזרים שם $1$ .

השיטה

ford_fulkerson(G=(V,E),s,t,c)
create f = 0
Gf = G , cf = c

while exists path P from s to t in Gf:
	cfp = min cf(u,v) from all (u,v) in P
	
	for each edge (u,v) in P:
		f(u,v) = f(u,v) + cfp
		cf(u,v) = cf(u,v) - cfp
		f(v,u) = f(v,u) - cfp
		cf(v,u) = cf(v,u) + cfp
		update(Gf.E)

בסוף השיטה הפונקצייה $f$ היא פונקציית הזרימה המקסימלית. נשים לב שמעדכנים את הקשתות ברשת השיורית, כל קשת שהקיבולת השיורית שלה התאפסה תוסר מהרשת השיורית, וכל קשת שהייתה מאופסת וכעת ערכה חיובי, תתווסף לרשת השיורית.
זאת, על-מנת שנדע באילו קשתות ניתן להשתמש במסלולים.

דוגמה

Pasted image 20230206211656.png
וערך הזרימה המקסימלית הוא $| f | = 23$
הבחנה מעניינת שכדאי לשים לב אליה היא שקשתות מהגרף המקורי יורדות לאורך האלגוריתם רק אם הן רוויות (שזה הגיוני מההגדרה אבל כדאי לראות זאת בדוגמה באופן מוחשי)

נכונות פורד־פולקרסון

כדי להתחיל להוכיח את הנכונות של השיטה הנ״ל נגדיר חתך $(s, t)$ .
הגדרה
חתך $(s, t)$ הוא חתך $(S, V - S)$ כאשר $s \in S$ ו $t, V - S$ .
נסמן $T = V - S$ מטעמי נוחות.

הקיבולת של חתך $(s, t)$ היא

c (S, T) = \sum_{(x, y) \in S \times T} c (x, y)

דוגמה:

Pasted image 20230206212836.png|250

\begin{matrix} S = {s, v_{1}, v_{2}, v_{3}} \\ T = {v_{4}, t} \\ c (S, T) = 2 + 2 + 4 = 8 \end{matrix}

למה
עבור רשת זרימה $G = (V, E)$ עם פונקציית קיבול $c$ וזרימה $f$ כלשהי ברשת.
לכל חתך $(S, T)$ מתקיים

| f | \leq c (S, T)

הוכחה
ראשית אנחנו כבר יודעים ש $| f | = f (S, T)$

| f | = f (S, T) = \sum_{(x, y) \in S \times T} f (x, y) \leq \sum_{(x, y) \in S \times T} c (x, y) = c (S, T)

האי שיוויון נובע מאילוץ הקיבול.

הבחנה

אנחנו יודעים אם כן שערך הזרימה חסום מלמעלה על ידי קיבולת חתך כלשהו. בפרט זה נכון על החתך עם הקיבולת המינימלית. מצד שני $f$ הייתה זרימה שרירותית. כלומר גם הזרימה עם הערך המקסימלי נסמנה $| f^{*} |$ חסומה מלמעלה על ידי חתך עם קיבולת מינימלית. בהמשך נראה שחתך המינימום הוא שווה בערכו לערך הזרימה.

Max Flow Min Cut
תהי $G = (V, E)$ רשת זרימה עם פונקציית קיבול $c$ וזרימה $f$ ברשת. השלושה הבאים שקולים:

$f$ זרימה עם ערך מקסימלי.
$G_{f}$ לא מכילה מסלולי שיפור.
קיים חתך $(S, T)$ ב $G$ כך ש $| f | = c (S, T)$

הוכחה
$2 \leftarrow 1$ :
נניח בשלילה שקיים מסלול שיפור ב $G_{f}$ ולכן יכולים לעבור על הקשתות שלו ולעדכן את הזרימה ובפרט לעדכן את הזרימה לקשת שיוצאת מ $s$ בסתירה למקסימליות של $f$ .

$3 \leftarrow 2$ :
נתבונן בחתך

S = {v \in V | s \to v i n G_{f}} \cup {s}

כלומר החתך שנפעיל על הגרף יהיה כל הקודקודים שקיים מסלול בגרף השיפור מ $s$ אליהם (כולל $s$ ).
זה הוא אכן חתך $(s, t)$ , זה נובע ישירות כי אנחנו מניחים ש $G_{f}$ לא מכילה מסלולי שיפור.
כעת עבור קשתות החתך נוכיח כ

\forall_{v \in T, u \in S} : f (u, v) = c (u, v)

מתנאי אילוץ הקיבול אנחנו יודעים שהזרימה בינהם קטנה או שווה מהקיבולת. נוכיח שהקיבולת במקרה הזה גדול או שווה מהזרימה כדי שיתקיים שיוויון.
נניח בשלילה ש $f (u, v) < c (u, v)$ . מהגדרת קיבלות שיורית מתקיים $c_{f} (u, v) = c (u, v) - f (u, v)$ כלומר במקרה הזה הקיבולת השיורית גדולה ממש מ $0$ . בגרף השיורי יתקיים אם כן ש $(u, v) \in E_{f}$ כלומר יש קשת חתך בגרף ולכן יש מסלול מ $s$ ל $t$ כי נוכל לבנות את המסלול

s \to u, v \to t

בסתירה לכך ש $t$ נמצאת ב $T$ . סה״כ מתקיים

| f | = f (S, T) = \sum_{(x, y) \in S \times T} f (x, y) = \sum_{(x, y) \in S \times T} c (x, y) = c (S, T)

$1 \leftarrow 3$ :
נניח בשלילה ש $f$ זרימה שערכה לא מקסימלי, כלומר עבור החתך $(S, T)$ שמקיים את $3$ ישנה זרימה $f^{'}$ כך ש

| f^{'} | > | f | = c (S, T)

בסתירה לכך שקיבולת חתך היא חסם עליון של כל זרימה.

נשים לב

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

זמן ריצה FORD-FULKERSON

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

זמן הריצה תלוי בבחירת מסלול השיפור יש לכך חשיבות קריטית ונראה שתי אלגוריתמים דיניץ ו אנמונדס-קארפ שכל אחד מהם בוחר את מסלול השיפור בצורה אחרת ויש לכך השפעה על זמן הריצה.
נשים לב שבכל איטרציה ערך הזרימה יגדל ב $1$ לפחות. כלומר זמן הריצה חסום על ידי $| f^{*} |$ כלומר על ידי ערך הזרימה של הזרימה האופטימלית. בכל איטרציה יש $O (| E |)$ עבודה מקומית ולכן החסם העליון לאלגוריתם הוא $O (| f^{*} | | E |)$ . זה יכול להיות גרוע מאוד למשל בדוגמה הבאה , צריך 2 מיליון איטרציות כדי לסיים.

Pasted image 20230206222049.png|300
הצוואר בקבוק ש $c (u, v)$ מייצר גורם לכך שתמיד יהיה מסלול מ $s$ ל $t$ כי כל איטרציה $c_{f} (P) = 1$ ולכן כל פעם נוסיף $1$ לזרימה של הקשתות עם קיבולת מיליון עד שנקבל מצב של רווייה עבורן. זה ייקח 2 מיליון איטרציות עד שנרווה את את קשתות אלו ולא יהיה מסלול מ $s$ ל $t$ .

אלגוריתם אדמונדס-קארפ

שיפור בזה אחר זה, ולא יעצור מעולם. אלגוריתם אדמונדס־קארפ הוא צורת מימוש אחת של שיטת פורד־פלקרסון. במימוש זה בכל שלב נמצא מסלול שיפור ברשת השיורית בעל מספר מינימלי של קשתות. מציאת המסלול מתבצעת על ידי הרצת BFS מ $s$ עד שמגיעים ל $t$ .

admonds_karp(G=(V,E),s,t,c):
	create f = 0
	Gf = G , cf = c

	while exists path P from s to t in Gf:
		find P using BFS
		cfp = min cf(u,v) from all (u,v) in P
	
		for each edge (u,v) in P:
			f(u,v) = f(u,v) + cfp
			cf(u,v) = cf(u,v) - cfp
			f(v,u) = f(v,u) - cfp
			cf(v,u) = cf(v,u) + cfp
			update(Gf.E)

נוכיח שהאלגוריתם מוצא זרימת מקסימום בתוך $O (| V | | E |)$ איטרציות כלומר זמן הריצה של האלגוריתם ביחד עם $B F S$ על כל איטרציה יהיה

O (| V | | E |^{2})

לפני כן, נגדיר $δ_{f} (u, v)$ כמרחק הקצר ביותר מ $u$ ל $v$ בגרף $G_{f}$ . ונשים לב שבכל איטרצייה באלגוריתם הנ״ך מוצאים מסלול שיפור באורך $δ_{f} (s, t)$ .

למה 1
תהי $f^{'}$ זרימה המתקבלת מזרימה $f$ על ידי שיפור על גבי מסלול באורך קצר ביותר מ $s$ ל $t$ ב $G_{f}$ . אזי

\forall_{u \in V} : δ_{f^{}} (s, u) \leq δ_{f^{'}} (s, u)

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

הוכחה:
נב״ש שקיים $u$ ככה ש

δ_{f} (s, u) > δ_{f^{'}} (s, u)

כיוון שקיימים כמה כאלה נניח בלי הגבלת הכלליות שבגרף $G_{f^{'}}$ מתקיים ש $u$ הוא הקודקוד עם המרחק המינימלי מ $s$ שמקיים את הנ״ל כלומר

\forall_{v \in G_{f^{'}} . V} : δ_{f^{'}} (s, v) < δ_{f^{'}} (s, u) \to δ_{f} (s, v) \leq δ_{f^{'}} (s, v)

כלומר אם המרחק הקצר ביותר בין $s$ לקודקוד $v$ כלשהו ברשת השיורית המשופרת קטן יותר מהמרחק הקצר ביותר בין $s$ ל $u$ באותה רשת שיורית אז הוא בהכרח קודקוד שעליו מתקיים התנאים שאנחנו רוצים להוכיח.

יהי $p$ מסלול קצר ביותר מ $s$ ל $u$ לאחר שיפור, כלומר ב $G_{f^{'}}$ . ויהי $v$ הקודקוד הקודם ל $u$ ב $p$ . אם כן עבור קודקוד $v$ מתקיים

δ_{f^{'}} (s, v) = δ_{f^{'}} (s, u) - 1, δ_{f} (s, v) \leq δ_{f^{'}} (s, v)

נחלק למקרים

א) אם $f (v, u) < c (v, u)$ אז הקשת $(v, u)$ קיימת גם ב $G_{f}$ והיא קיימת גם ב $G_{f^{'}}$ כי היא אינה רוויה ולכן

δ_{f} (s, u) \leq δ_{f} (s, v) + 1 \leq δ_{f^{'}} (s, v) + 1 = δ_{f^{'}} (s, u)

בסתירה להנחה.

ב. אם $f (v, u) = c (v, u)$ אז הקשת רוויה ולכן בכלל לא נמצאת ב $G_{f}$ . כלומר מסלול השיפור שלנו חייב לעבור דרך הקשת $(u, v)$ כדי שלאחר שיפור הקשת $(v, u)$ תכנס ל $G_{f^{'}}$ . המשמעות היא כעת ש $u$ מקדימה את $v$ במסלול השיפור ולכן

δ_{f} (s, u) = δ_{f} (s, v) - 1 \leq δ_{f^{'}} (s, v) - 1 = δ_{f^{'}} (s, u) - 2 \leq δ_{f^{'}} (s, u)

בסתירה.

מסקנה
תהי $f^{'}$ זרימה המתקבלת מזרימה $f$ על ידי שיפור על גבי מסלול באורך קצר ביותר מ $s$ ל $t$ ב $G_{f}$ . אזי

\forall_{u \in V} : δ_{f^{}} (u, t) \leq δ_{f^{'}} (u, t)

נרצה להראות שיש קשר בין המסלולים הקצרים ביותר מ $s$ ל $t$ ב $G_{f}$ והמסלולים הקצרים ביותר מ $s$ ל $t$ ב $G_{f^{'}}$ , אם המרחק מ $s$ ל $t$ לא השתנה.

למה 2
תהי $f^{'}$ זרימה המתקבלת מזרימה $f$ על ידי שיפור על גבי מסלול באורך קצר ביותר מ $s$ ל $t$ ב $G_{f}$ אזי אם $δ_{f} (s, t) = δ_{f^{'}} (s, t)$ אז כל מסלול קצר ביותר מ $s$ ל $t$ בגרף המשופר $G_{f^{'}}$ הוא גם מסלול קצר ביותר מ $s$ ל $t$ ב $G_{f}$ (יחס הכלה).

אינטואיצייה- כל איטרצייה על מסלול כלשהי אנחנו מרווים קשת ולכן שיפור של מסלול קצר ביותר חייבת לגרום ל״ניתוק״ של אותו מסלול מ $s$ ל $t$ . אם כן אם האורך של המסלולים הקצרים ביותר לא השתנה לאחר השיפור המשמעות היחידה שיכולה להיות היא שהיה מסלול אחר בגרף לפני השיפור שפשוט לא תפסנו אותו בריצת BFS..

הוכחה
יהי $p$ המסלול הקצר ביותר מ $s$ ל $t$ ב $G_{f^{'}}$ כך ש $| p | = δ_{f} (s, t) = δ_{f^{'}} (s, t)$ , נניח בשלילה כי $p$ לא נמצא ב $G_{f}$ . אזי $p$ בהכרח מכיל לפחות קשת חדשה אחת. נסמן קשת זו $(v, u)$ ונקרא לה קשת חדשה.

הגדרה: קשת $(u, v)$ תקרא חדשה אם הקשת $(v, u)$ הייתה ב $G_{f}$ ומסלול השיפור כלל אותה.
נשים לב שקשתות שיכולות להתווסף לגרף רק במצבים שבהם הזרמתי זרם בקשת כלשהי וזה עדיין לא הרווה אותה , במצב זה הקשת המקורית לא אמורה להעלם, או שהרוותי את הקשת ואז היא יורדת והקשת הנגדית לה נכנסת .

כיוון שהמסלול ששיפרנו הוא הקצר ביותר גם כן אז $(u, v)$ נמצא על המסלול הקצר ביותר הזה ומתקיים $δ_{f} (s, u) = δ_{f} (s, v) + 1$ .

על פי הטענות הקודמות שהוכחנו אנחנו יודעים ש

δ_{f^{'}} (s, v) \geq δ_{f} (s, v) a n d δ_{f^{'}} (u, t) \geq δ_{f} (u, t)

כיוון ש $p$ מסלול קצר ביותר מ $s$ ל $t$ ב $G_{f^{'}}$ ואנחנו יודעים ש $(v, u)$ היא קשת במסלול אזי

\begin{matrix} δ_{f^{'}} (s, t) = | p | \\ = δ_{f^{'}} (s, v) + 1 + δ_{f^{'}} (u, t) \\ \geq δ_{f} (s, v) + 1 + δ_{f} (u, t) \\ = δ_{f} (s, u) + 1 + 1 + δ_{f} (u, t) \\ = δ_{f} (s, t) + 1 \\ > δ_{f} (s, t) \end{matrix}

בסתירה לנתון.

הבחנה

כאשר זרימה $f^{'}$ מתקבלת מזרימה $f$ על ידי שיפור מסלול $p_{f}$ הקצר ביותר, אזי מסלול זה לא יכול להיות קיים ב $G_{f^{'}}$ כיוון שלפחות אחת מהקשתות שלו נהיית רוויה.

תובנה זאת תוביל אותנו ללמה הבאה:
תהי $G$ רשת זרימה ו $f$ זרימה כלשהי. נתבונן באלגוריתם שמשפר על גבי מסלולים מאורך קצר ביותר מ $s$ ל $t$ רק כל עוד אורכם הוא $δ_{f} (s, t)$ . אזי, מרגע שקשת $(u, v)$ נהיית רוויה על ידי האלגוריתם, קשת זאת לא תהיה בשימוש על ידי אף מסלול שיפור אחר בהמשך ריצת האלגוריתם.

הוכחה: נסתכל מה קורה לקשת $(u, v)$ כאשר הזרימה היא $f^{'}$ ואנחנו יודעים ש $δ_{f^{'}} (s, t) = δ_{f} (s, t)$ .
ראשית נשים לב שמשמעות הדבר היא שיש מספר מסלולים קצרים ביותר בגרף המקורי וכל פעם אנחנו משפרים אחד מהם. אם הרוונו את הקשת $(u, v)$ בריצה על המסלול הקצר ביותר הזה, מהגדרת הקיבולת השיורית היא אמורה להיות כעת $0$ ולכן לשיפור הבא הקשת הזאת לא תכנס. כמובן שלאחר שיפור כלשהו שקרה לקשת הזאת אז $(v, u)$ נכנסה כקשת חדשה אבל נשים לב שמהלמה הקודמת אנחנו יודעים שאם אורכי המסלולים הקצרים שווים לאחר שיפור אז כל מסלול קצר ביותר ברשת השיורית המשופרת היא גם מסלול קצר ביותר ברשת השיורית הקודמת לה. כיוון ש $(v, u)$ נכנסה רק לאחר שיפור כלשהו הרי שבגרף המקורי היא לא הייתה חלק מהמסלולים הקצרים ביותר ולכן גם באיטרציות הבאות לא נשתמש בה .

זמן ריצה

פאזה

נגדיר את הפאזה ה $i$ באלגוריתם של אדמונדס קארפ כסדרת האיטרציות שבהן אורך המסלול הקצר ביותר הוא $i$ קשתות.

נשים לב שכל מסלול שיפור בפאזה ה $i$ ניתן לשייך לקשת אחת לפחות שאותה הוא הפך לרוויה על פי הטענה שהוכחנו למעלה אנחנו יודעים שכל קשת רוויה תשויך למסלול אחד בפאזה ה $i$ בלבד, ולכן סה״כ בפאזה ה $i$ יכולות להיות לכל היותר $| E |$ איטרציות בכל פאזה.

נשים לב שיכול להיות מקרה שבו המרחק בין $s$ ל $t$ הקצר ביותר עולה ב $1$ אחרי כל שיפור כלומר בהתחלה הוא $1$ ואחרי זה $2$ עד שמגיע ל $| V |$ המסלול הארוך ביותר בגרף המקורי. כלומר יש לכל היותר $| V | - 1$ מרחקים אפשריים של $s$ ו $t$ ולכן מספר הפאזות הוא $O (| V |)$ .

סך אם כן מספר האיטרציות הוא מספר הפאזות כפול מספר האיטרציות לפאזה כלומר $O (| V | | E |)$

בגלל הפעלת BFS בכל איטרציה שלוקחת $O (| E |)$ יתקיים ש זמן הריצה הכולל הוא

O (| V | | E |^{2})

אלגוריתם דיניץ

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

גרף השכבות

האלגוריתם של דיניץ בונה גרף שכבות $L$ בתחילת כל פאזה. בפאזה ה $i$ הגרף $L$ מכיל $i + 1$ שכבות. השכבה ה $i$ מכילה את כל הקודקודים $u \in V$ כך ש $δ_{f} (s, u) = i$ כש $f$ הוא הזרימה הנוכחית ו $u$ הוא על מסלול קצר ביותר כלשהו מ $s$ ל $t$ . הקשתות ב $L$ הן קשתות שנמצאות על מסלול קצר ביותר כלשהו מ $s$ ל $t$ ב $G_{f}$ .

Pasted image 20230207020142.png|450

הקודקוד היחיד שאורך המסלול הקצר ביותר מ-s אליו הוא 0 ,הוא רק s. הקודקודים בשכבה
הבאה יהיו הקודקודים שאורך המסלול הקצר ביותר מ-s אליהם הוא 1 ,והם נמצאים על מסלול
קצר ביותר כלשהו מ-s ל-t.

הקודקוד היחיד שיימצא בשכבה האחרונה כמובן הוא $t$ שכן מהגדרת פאזה יתקיים $δ_{f} (s, t) = i$ . לא יתכנו קודקודים נוספים בשכבה זו שכן אם היה אחד נוסף אז הוא לא אמור להיות חלק מהמסלול הקצר ביותר מ $(s, t)$ .

בנייה של גרף שכבות לוקחת $O (| V | + | E |)$ זמן למשל גרף השכבות עבור הגרף הבא ייראה

Pasted image 20230206161005.png|250

IMG_B8D6CADD1718-1.jpeg|350

מציאת מסלול שיפור קצר ביותר בעזרת גרף השכבות.

לפי הבנייה של $L$ כל קשת ב $L$ נמצאת על מסלול קצר ביותר מ $s$ ל $t$ , לכן בחירה של קשת שרירותית בשכבה שעליה אנחנו נמצאים בהכרח תביא אותנו ל לקודקוד בשכבה הבאה כלומר כל פעם נבחר קודקוד עד שנגיע ל $t$ וזה יהיה המסלול הקצר ביותר שנעבוד איתו. זה לוקח $O (i)$ זמן כלומר כאורך המסלול הקצר שזה בעצם מיוצג על ידי $i$ .

find_shortest_path(L, s, t)
	u = s
	P = {}
	while (u != t)
		choose arbitrary edge (u,v) 
		add (u,v) to P
		u = v
	return P

בעיה

כעת, בנינו את $L$ בזמן $O (| E |)$ ומצאנו מסלול קצר ביותר בזמן $O (i)$ . אבל אחרי שמצאנו את מסלול, אנחנו יודעים בוודאות שנרווה קשת , כי קשת אחת מוצמדת לריצה אחת של פאזה ונצטרך למחוק אותה מ $L$ וכמובן לעדכן את השכבות שכן יכולות להתווסף עוד שכבות. כמו כן בעיה נוספת שעולה היא שקודקוד כלשהו $u$ עלול להיות לא רלוונטי לאחר רוויה של קשת , כלומר אי אפשר להגיע ממנו ל $t$ .

פתרון:
נשים לב ש $u$ צריך להיות מוסר מ $L$ אמ״מ דרגת הכניסה או היציאה שלו היא $0$ . נקרא לקודקוד זה מבוי סתום.
כלומר באופן אינטואיטיבי אחרי ביצוע שיפור נרצה להוריד את כל הקודקודים שעונים להגדרה של מבוי סתום ביחד עם הקשתות שקשורות אליהם עד שאין עוד מבוי סתום. הפתרון הפשוט ביותר הוא להחזיק שתי מונים לכל קודקודים עבור דרגת כניסה ויציאה וברגע שאלו מתאפסים להוריד את המבוי הסתום ואת הקשתות שקשורות אליו.
נשים לב, יכולים להיות מספר מבויים סתומים שצריך להסיר אחרי איטרצייה בודדת. אבל מהלמה שהוכחנו כל קודקוד יהפוך להיות מבוי סתום לכל היותר פעם אחת בפאזה ולכן הוא גם יימחק מ $L$ לכל היותר פעם אחת בפאזה. כנ״ל לגבי הקשתות. אם כן זמן הריצה הכולל לעדכון $L$ הוא $O (| V | + | E |) = O (| E |)$ .

הבחנה

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

האלגוריתם

Dinic(G=(V,E),s,t,c)
	init f = 0
	Gf = G , cf = c

	while exists path P from s to t in Gf:
	\\ this will occur each phase change
		build L 
		cfp = min cf(u,v) from all (u,v) in P
	
		where exists a path P from s to t in L:
			for each (u,v) in P:
				f(u,v) = f(u,v) + cfp
				cf(u,v) = cf(u,v) - cfp
				f(v,u) = f(v,u) - cfp
				cf(v,u) = cf(v,u) + cfp
				update(Gf.E)

			update L by removing dead ends

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

זמן ריצה

בזכות התכונות שהוכחנו אנחנו יודעים שגרף השכבות תמיד יגדל, כלומר מקסימום $O (| V |)$ פאזות.
בניית גרף השכבות לוקחת $O (| E |)$ פר פאזה, נסמן $k$ כמספר האיטרציות בפאזה ו $i$ זה מספר השכבות כלומר עלות העדכון חסומה במספר השכבות. לכן כל פאזה תעשה $k \cdot l$ עדכונים. אם כן זמן הריצה יהיה

O (| E | + k \cdot l)

מהתכונות שהוכחנו אנחנו יודעים שקשת אחת מוצמדת לריצה אחת של פאזה ולכן $k \leq O (| E |)$ ו $l$ חסום באורך המסלול הארוך ביותר האפשרי שהוא $| V |$ וסך הכל זמן הריצה לפאזה הוא

O (| E | + k \cdot l) = O (| E | + | E | \cdot | V |) = O (| E | \cdot | V |)

נכפיל במספר הפאזות ונקבל

O (| E | | V |^{2})

זיווגים בגרף דו צדדי

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

זיווג בגרף $G = (V, E)$ גרף לא מכוון הוא תת קבוצה של קשתות הגרף $M \subseteq E$ אם היא מקיימת ש $\forall_{v \in V} \deg_{M} (v) \leq 1$ כאשר $\deg_{M} (v)$ זה מסמן את הדרגה של $v$ בגרף המושרה על ידי $M$ כלומר $G^{'} (V, M)$ .
קודקוד שדרגתו $1$ ייקרא מזווג וקודקוד שדרגתו $0$ בגרף המושרה ייקרא לא מסווג. ניתן להגדיר את $M$ גם כתת קבוצה של הקשתות כך שלאף $2$ מהן אין קודקוד משותף.

זיווג מקסימלי
זיווג $M$ יהיה מקסימלי אם לא ניתן להוסיף לא קשתות, באופן פורמלי המשמעות היא שלא קיים זיווג $M^{'}$ כך ש $M^{'} \subset M$ .

הבחנה

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

זיווג מקסימום
נאמר ש $M$ הוא זיווג מקסימום אם לכל זיווג $M^{'}$ מתקיים $| M | \geq | M^{'} |$ .

Pasted image 20230207113658.png|350
ניתן לראות משמאל זיווג מקסימום ובאמצע זיווג מקסימלי על הגרף מימין.

מציאת זיווג מקסימלי

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

גרף דו צדדי
נאמר ש $G = (V, E)$ הוא גרף דו צדדי אם ורק אם ניתן לחלק את $V$ לשני חלקים : $L, R$ כך שיתקיים $L \cup R = V$ וגם $L \cap R = \emptyset$ וכל הקשתות בגרף יקיימו שצד שמאל של הזוג שייך ל $L$ וצד ימין שייך ל $R$ . באופן פורמלי

\forall_{(u, v) \in E} : (u, v) \in L \times R

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

רדוקצייה מבעיית זיווג מקסימום לבעיית זרימת מקסימום

נראה כי ניתן לפתור את בעיית זיווג מקסימום בגרף הדו צדדי $G$ על ידי פתרון זרימת מקסימום בגרף אחר
יהי $G = (L, R, E)$ גרף דו צדדי (זה סימון מקובל לגרף כזה). נבנה רשת זרימה $G^{'} = (V^{'}, E^{'})$ באופן הבא

\begin{matrix} V^{'} = V \cup {s, t} \\ E^{'} = {(s, u) | u \in L} \cup {(u, v) | (u, v) \in L \times R} \cup {(v, t) | v \in R} \\ \forall_{e \in E^{'}} : c (e) = 1 \end{matrix}

בעצם חיברנו את קודקוד המקור ברשת הזרימה לכל $L$ ואת קודקוד ה״בור״ לכל $R$ . לבסוף הקיבולת של כל קשת היא 1. כמובן גם שבמצב זה אנחנו ״מכוונים״ את $G$ כי רשת זרימה היא על גרף מכוון.

למה
אם $M$ הוא זיווג ב $G$ אז קיימת ב $G^{'}$ זרימה $f$ המקיימת $| f | = | M |$ .
אם $f$ זרימה בערכים שלמים ב $G^{'}$ אז קיים זיווג $M$ ב $G$ כך ש $| M | = | f |$

הוכחה
א) נניח $M$ הוא זיווג ב $G$ - הרעיון הוא להעביר את הזרימה רק דרך הקשתות שבזיווג . אם כן ניקח את הזיווג של $G$ ונכוון את הזרימה שם מ $L$ ל $R$ . כמו כן לכל קודקוד $u$ ב $L$ שהוא גם ב $M$ נעביר על הקשת $(s, u)$ זרימה $1$ וגם באופן דומה לכל קודקוד $v$ ב $R$ שהוא גם ב $M$ נעביר על הקשת $(v, t)$ זרימה $1$ .

Pasted image 20230207121813.png|350

נשים לב שנוכל להגדיר את הקודקודים כחתך $({s} \cup L, V - {s} \cup L) = ({s} \cup L, R \cup {t})$ שזה חתך $(s, t)$ ואנחנו יודעים ש

f ({s} \cup L, R \cup {t}) = | f |

כיוון שאנחנו מזרימים רק דרך הקשתות ב $M$ וכל קשת מזרימה $1$ מהגדרת פונקציית הקיבולת אז אנחנו יודעים:

f ({s} \cup L, R \cup {t}) = | M | = | f |

ב) נניח ש $f$ זרימה בערכים שלמים. נסתכל על הזיווג הבא

M = {(u, v) | f (u, v) > 0, (u, v) \in L \times R}

זה בעצם המקרה הסימטרי למה שעשינו קודם. מגדירים זיווג רק היכן שהזרימה היא $1$ בין קשתות גרף הדו צדדי. אם כן

\begin{matrix} | M | = f (L, R) = f (L, V^{'}) - f (L, L) - f (L, s) - f (L, t) = 0 - 0 + f (s, L) - 0 = f (s, L) \end{matrix}

נשים לב ש $f (L, V^{'})$ זה בעצם סכימת הזרימה של כל הקודקודים שיוצאים מ $L$ לכל קודקוד אחר. אנחנו יודעים שהזרימה מגיע ל $L$ רק מ $s$ והיא עוברת ל $R$ דרכם. כמו כן מסימטריה יש זרימה נגדית שעוברת מ $L$ ל $s$ כשכל קודקוד שעוברת בו זרימה $1$ מעביר $- 1$ לצד השני ולכן כל זרימה שעוברת ל $R$ מתבטלת כאשר סוכמים עם הזרימה הנגדית שחוזרת ל $s$ .

אם נמשיך נקבל תחת אותו ההסבר

f (s, L) = f (s, V^{'}) - f (s, R) - f (s, t) = f (s, V^{'}) - 0 - 0 = | f |

למה
אם לכל קשת $(u, v) \in E$ מתקיים שהוא בעל קיבולת טבעית אז קיימת זרימת מקסימום בה כך ש $\forall_{u, v \in V} : f (u, v) \in Z$ .

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

אם כן האלגוריתם בפסודו קוד :

max-matching(G=(L,R,E))
	create G' and c
	ford_fulkerson(G',s,t,c)
	M = {all (u,v) in LxR where f(u,v)>0 in G'}
	return M

זמן הריצה תלוי בהרצה פשוטה של פורד-פולקרסון כלומר $O (| f^{*} | | E |)$ שזה ערך זרימת המקסימום בגרף , זאת חסומה , כיוון שהקיבולת היא רק $1$ על ידי $| V |$ ולכן סך הכל זמן הריצה הוא $O (| E | | V |)$ .

אלגוריתם הופקרופט-קארפ

אלגוריתם זה מאפשר למצוא זיווג מקסימום בזמן $O (| E | \sqrt{| V |})$ .
האלגוריתם הזה הוא ניתוח הדוק יותר לאלגוריתם של דיניץ על הגרף $G^{'}$ רשת הזרימה שבנינו מגרף דו״ץ $G$ כלשהו.

כיוון שאנחנו נעבוד רק על $G^{'}$ בהסבר הזה , לשם הנוחות אסמן אותו כ $G = (V, E)$ .
שתי תכונות חשובות של $G$ שנעזר בהן

א) לכל זוג קודקודים $u, v \in V$ מתקיים $c (u, v) \in {0, 1}$ ואם $c (u, v) = 1$ אז $c (v, u) = 0$ .
ב) לכל $u \in V - {s, t}$ מתקיים $\deg_{i n} (u) = 1$ או $\deg_{o u t} (u) = 1$ .

הבחנה

לאורך כל הרצת השיטה של פורד לא משנה באיזה מימוש על $G$ , כל הרשתות השיוריות מקיימות את התכונות הנ״ל.
כלומר עבור $f^{'}$ זרימה המתקבלת מ $f$ על ידי שיפור. אם $G_{f}$ מקיים את התכונות הנ״ל אז גם $G_{f^{'}}$ .
ההוכחה מבוססת על כך שסעיף א מתקיים מהגדרת הקיבולת השיורית וגם שכל שיפור שאעשה תמיד יהיה על ידי הזרמת $1$ מ $s$ למסלול שבחרתי עד שיגיע ל $t$ ההזרמה הזאת גורמת לכל המסלול להיות רווי ולכן מה שיקרה כל המסלול ייעלם ויופיעו קשתות חדשות שהן בעצם המסלול לאחר reverse והוא כמובן עדיין מקיים את התכונה הזאת.

למה 1
ברשת זרימה המקיימת את התכונות הנ״ל אם המסלול הקצר ביותר מ $s$ ל $t$ הוא באורך $i > 1$ אזי, ערך זרימת המקסימום הוא לכל היותר

\frac{| V | - 2}{i - 1} = O (\frac{| V |}{i})

אינטואיצייה על גרף דו צדדי כיוון שמדובר בבניית רשת זרימה לגרף דו״צ ומהגדרת איך שהוא בנוי אנחנו יודעים שערך זרימת המקסימום הוא מספר הקשתות בזיווג מקסימום . במצב הכי אידיאלי יתקיים שכל הקשתות בין $L$ ו $R$ שייכות לזיווג זה. במצב זה המשמעות היא שמזרימים $1$ מ $s$ לכל קודקודי $L$ ואלו מזרימים את זה לקודקוד המתאים ב $R$ ומשם ל $t$ . מהגדרת זיווג אנחנו יודעים שכל קשת בין שתי קודקודים היא ייחודית כלומר אם $(v_{i}, u)$ היא קשת במצב הזה אז אין קשת $(v_{j}, u)$ כלומר ערך הזרימה המקסימלי הוא בידיוק מספר הקודקודים ש $s$ מזרים אליהם שזה כל $L$ כלומר מספר הקודקודים בלי קודקודי $s, t$ חלקי $2$ . המסלול הארוך ביותר במצב זה הוא באורך $3$ ולכן ערך זרימת המקסימום הוא לכל היותר

\frac{| V | - 2}{3 - 1} = \frac{| V | - 2}{2}

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

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

מההבחנות שעשינו נקבל שזמן הריצה לפאזה הוא

O (| E | + k \cdot l) = O (| E | + \frac{| V |}{i} \cdot i) = O (| E | + | V |) = O (| E |)

$k$ חסום בזה בגלל שהמשמעות היא שכל שיפור אנחנו יכולים להצמיד את כל קשתות המסלול שלקחנו שבמקרה הזה חסום ב $\frac{| V |}{i}$ .
סך הכל לאחר $| V |$ פאזות נקבל זמן ריצה

O (| E | | V |)

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

הבחנה

אם $i \geq \sqrt{V}$ אז ערך זרימת המקסימום עבור רשת המקיימת את הדרוש חסום ב $O (\frac{| V |}{i}) = O (\sqrt{| V |})$

אם כן נוכל להריץ את האלגוריתם של דיניץ על $G$ עד הרגע שהמרחק בין $s$ ל $t$ גדול מ $\sqrt{| V |}$ כלומר על $\sqrt{| V |}$ הפאזות הראשונות. כעת יש $O (\sqrt{| V |})$ פאזות ולכן זמן הריצה הכולל לחלק הזה מסתכם בלכל היותר $O (\sqrt{| V |} | E |)$ . נוכל להריץ איזה שיטה שנרצה על הרשת השיורית כעת כלומר עבור $\sqrt{| V |}$ הפאזות הנותרות בזמן $O (\sqrt{| V |} | E |)$ ונקבל אלגוריתם שבחלקו הראשון מריץ דיניץ ובחלקו השני מריץ איזה שיטה שנבחר והזרימה הכוללת תהיה

O (\sqrt{| V |} | E | + \sqrt{| V |} + | E |) = O (\sqrt{| V |} + | E |)