רשת זרימה

מתוך ויקיפדיה, האנציקלופדיה החופשית

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

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

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

תוכן עניינים

1 הגדרה פורמלית
- 1.1 רשת זרימה
- 1.2 זרימה
2 שיטת פורד-פולקרסון
3 שיטת הרם-וקדם
4 יישומים
- 4.1 גרפים דו צדדיים
5 לקריאה נוספת

[עריכה] הגדרה פורמלית

[עריכה] רשת זרימה

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

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

[עריכה] זרימה

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

בצורה פורמלית, ניתן לתאר זרימה על ידי פונקציית זרימה $\ f:V\times V\to\mathbb{R}$ . פונקציה זו מתאימה לכל זוג צמתים $\ (u,v)$ את כמות הזרימה מ- $\ u$ אל $\ v$ (לכיוון יש חשיבות), כך שמתקיימים התנאים הבאים:

אנטי-סימטריה: $\ f(u,v)=-f(v,u)$
שמירה על אילוץ הקיבול: $\ f(u,v)\le c(u,v)$
שימור הזרימה: לכל $\ u\ne s,t$ מתקיים: $\ \sum_{v\in V}f(u,v)=0$

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

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

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

לכל זרימה מגדירים את ערך (או כמות) הזרימה בתור $\ |f|=\sum_{v\isin V}f(s,v)$ , כלומר כמות הזרימה נטו שיוצאת מן המקור. ניתן להראות בהתבסס על תכונות הזרימה כי כמות זו שווה לכמות הזרימה נטו שנכנסת אל הבור. על כן, ניתן לחשוב על ערך הזרימה בתור כמות הזרימה שעוברת ברשת הזרימה ביחידת זמן.

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

[עריכה] שיטת פורד-פולקרסון

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

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

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

[עריכה] רשת שיורית

בהינתן זרימה, ניתן לבדוק כיצד ניתן לשפר אותה (כלומר, להגדיל את ערך הזרימה) באמצעות שימוש בגרף המכונה "הרשת השיורית", אשר מייצג את הקשתות שדרכן ניתן להגדיל את הזרימה.

מבחינה פורמלית, לכל זוג צמתים $\ (u,v)$ מגדירים את הקיבול השיורי של $\ (u,v)$ על ידי:

$\ c_f(u,v)=c(u,v)-f(u,v)$

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

הרשת השיורית היא גרף מכוון שצמתיו הם צומתי רשת הזרימה המקורית, ויש בו קשת בין כל זוג צמתים שעבורו $\ c_f(u,v)>0$ . כלומר, הגרף מייצג את כל המקומות שבהם ניתן להעביר זרימה נוספת ברשת המקורית.

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

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

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

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

[עריכה] מימוש שיטת פורד-פולקרסון

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

לכל קשת בצע:
1. $\ f(u,v)=0$
2. $\ f(v,u)=0$
כל עוד קיים מסלול מ- אל ברשת השיורית המושרית על ידי , בצע, עבור מסלול מסוים:
1. $\ c_f(p)=\min\left\{c_f(u,v)|(u,v)\isin p\right\}$
2. לכל קשת בצע:
  1. $\ f(u,v)=f(u,v)+c_f(p)$
  2. $\ f(v,u)=-f(u,v)$

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

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

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

עם זאת, גם כאשר מובטח כי האלגוריתם יסיים את ריצתו, סיבוכיות הזמן תלויה בערכה המקסימלי של פונקציית הזרימה: ניתן להראות כי הוא $\ O(E|f^*|)$ , כאשר $\ f^*$ הוא ערך הזרימה המקסימלי.

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

[עריכה] אלגוריתם אדמונדס-קארפ

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

ניתן להוכיח כי סיבוכיות הזמן של אלגוריתם זה היא $\ O(VE^2)$ . סיבוכיות זו נובעת משני גורמים: ראשית, הרצת אלגוריתם חיפוש לרוחב דורשת באופן כללי זמן של $\ O(E)$ , ומתבצעת הרצה אחת של האלגוריתם בכל איטרציה. גם שיפור הזרימה בכל איטרציה דורש זמן של $\ O(E)$ . ניתן להראות כי מספר האיטרציות הוא לכל היותר $\ O(VE)$ . כדי לראות זאת משתמשים במושג של קשת קריטית - קשת המופיעה בגרף השיורי באיטרציה i אך לא באיטרציה i+1. עבור אלגוריתם אדמונדס-קארפ מתקיימת התכונה כי אם קשת $\ (u,v)$ שהייתה קריטית באיטרציה מסוימת שבה והופיעה באיטרציה מאוחרת יותר, אז המרחק בין $\ u$ ו- $\ s$ בגרף השיורי גדל לפחות ב-2 בין האיטרציות, ולכן קשת לא יכולה להיות קריטית יותר מ- $\ O(V)$ פעמים (כי אורך מסלול בגרף הוא $\ O(V)$ ), ומכיוון שמספר הקשתות בגרף השיורי הוא $\ O(E)$ (לכל קשת בגרף המקורי יש לכל היותר שתי קשתות בגרף השיורי) ובשל העובדה שבכל איטרציה יש לפחות קשת קריטית אחת, נובע כי יש לכל היותר $\ O(VE)$ איטרציות.

[עריכה] אלגוריתם דיניץ

אלגוריתם דיניץ דומה לאלגוריתם אדמונדס-קארפ, אך הוא מתוחכם ממנו, והדבר בא לידי ביטוי בחסם קטן יותר על זמן הריצה, של $\ O(V^2E)$ . הרעיון הבסיסי באלגוריתם הוא זה של שיטת פורד-פולקרסון - מציאת מסלול שיפור, ושיפור הזרימה לאורכו, אך האלגוריתם של דיניץ מאפשר למצוא מספר מסלולי שיפור "בבת אחת", ובצורה יעילה יותר מאשר באלגוריתם אדמונדס-קארפ. האלגוריתם מבוסס על מושג נוסף לזה של הגרף השיורי - גרף השכבות. בהינתן זרימה וגרף שיורי עבורה, גרף השכבות בנוי על הגרף השיורי, ומחולק ל"שכבות" על פי מרחקי הצמתים שבכל שכבה מהצומת $\ s$ - בשכבה ה- $\ k$ נמצאים כל הצמתים שמרחקם מ- $\ s$ הוא בדיוק $\ k$ (כאן מרחק הוא מספר הקשתות שיש לעבור במסלול המחבר את שני הצמתים).

הקשתות היחידות שבגרף השכבות הן אלו שמחברות בין צמתים השייכים לשתי שכבות סמוכות (כלומר, כל קשת שייכת למסלול קצר ביותר מ- $\ s$ אל איזה שהוא צומת).

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

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

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

[עריכה] שיטת הרם-וקדם

שיטת הרם-וקדם מייצגת גישה שונה לפתרון בעיית זרימת המקסימום, שאינה דומה לשיטת פורד-פולקרסון. ניתן לממש אותה באופן יעיל כך שיתקבל אלגוריתם שזמן הריצה שלו הוא $\ O(V^3)$ - שיפור יחסי לזמני הריצה של מימושי שיטת פורד-פולקרסון עבור גרפים בעלי קשתות רבות.

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

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

כדי להבטיח את עצירת האלגוריתם במהירות, לא מתירים העברת זרימה מכל צומת לשכנה שלה, אלא מגדירים כלל נוסף, המבוסס על תכונת "גובה" של הצמתים. בגרף בעל n צמתים נותנים תחילה לכל הצמתים פרט למקור את הגובה 0, ולמקור נותנים גובה n. לאחר ההזרמה הראשונית מהמקור לשכניו, מתקיים הכלל הבא: מותר לצומת להזרים רק לצומת שקטן ממש ממנו (ניתן לדרוש אף שהפרשי הגבהים ביניהם יהיו בדיוק 1). כדי לאפשר שימוש בכלל זה מגדירים פעולה נוספת שאותה האלגוריתם מסוגל לבצע - הרמת צומת כך שיהיה גבוה מכל שכניו הרלוונטיים (זוהי פעולת ה"הרם" שבשם השיטה, ובאנגלית Lift או Relabel). הגובה נבחר בתור הגובה המינימלי הדרוש שעבורו הצומת יהיה גבוה מכל השכנים שעוד ניתן להזרים אליהם (כלומר, שהקשת אליהם אינה רוויה).

במימוש הנאיבי של שיטת הרם-וקדם, האלגוריתם הוא כדלהלן:

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

מימוש זה מבטיח זמן ריצה של $\ O(V^2E)$ . כדי להבטיח זמן ריצה של $\ O(V^3)$ משכללים את דרך הבחירה של הצומת שעליה יבוצעו פעולות ההרם-וקדם, כך שהאלגוריתם מתמקד בכל פעם בצומת בודד ומרוקן אותו לחלוטין.

[עריכה] יישומים

[עריכה] גרפים דו צדדיים

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

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

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

[עריכה] לקריאה נוספת

תומאס ה. קורמן, צ'ארלס א. לייזרסון, רונאלד ל. ריבסט, מבוא לאלגוריתמים, הוצאת MIT (פרק 26), תורגם לעברית על ידי האוניברסיטה הפתוחה.
שמעון אבן (1979), Graph Algorithms, הוצאת Computer Science Press.

קטגוריות: תורת הגרפים | אלגוריתמים בתורת הגרפים

See also ebooksgratis.com: no banners, no cookies, totally FREE.