רשת זרימה

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

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

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

הגדרה פורמלית

רשת זרימה

רשת זרימה מורכבת מגרף $\ G=(V,E)$, משני צמתים מיוחדים - המקור (Source) $\ s\in V$ והבור (Sink) $\ t\in V$, ומפונקציית קיבול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c:V\times V\to\mathbb{R}^{+}\cup\left\{0,\infty\right\}} שמתאימה לכל זוג צמתים את כמות הזרימה המקסימלית שיכולה לעבור מהראשון שבהם אל השני (ויכולה להיות אינסופית, כלומר ללא הגבלה). אם לא קיימת קשת מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} , מניחים כי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ c(u,v)=0} .

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

זרימה

ערך מורחב – בעיית זרימה

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

בצורה פורמלית, ניתן לתאר זרימה על ידי פונקציית זרימה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f:V\times V\to\mathbb{R}} . פונקציה זו מתאימה לכל זוג צמתים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ (u,v)} את כמות הזרימה מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} (לכיוון יש חשיבות), כך שמתקיימים התנאים הבאים:

1. אנטי-סימטריה: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(u,v)=-f(v,u)}
2. שמירה על אילוץ הקיבול: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ f(u,v)\le c(u,v)}
3. שימור הזרימה: לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u\ne s,t} מתקיים: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \sum_{v\in V}f(u,v)=0}

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

תכונת האנטי סימטריה נועדה להקל על הטיפול המתמטי ברשת הזרימה. מכיוון שזרימה שעוברת מצומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} אל הצומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} מתוארת על ידי מספר חיובי (כמות הזרימה שעברה), ניתן לחשוב על כך כאילו הזרימה עברה מהצומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} (כלומר, בכיוון השני) אך בכמות שלילית. הדבר מקל, לדוגמה, על כתיבת האילוץ השלישי, ומאפשר לדבר על הזרימה בין שני צמתים בשני הכיוונים גם יחד, ולא רק בכיוון אחד, גם אם קיימת קשת ביניהם רק בכיוון אחד.

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

לכל זרימה מגדירים את ערך (או כמות או שטף) הזרימה בתור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ |f|=\sum_{v\isin V}f(s,v)} , כלומר כמות הזרימה נטו שיוצאת מן המקור. ניתן להראות בהתבסס על תכונות הזרימה כי כמות זו שווה לכמות הזרימה נטו שנכנסת אל הבור. על כן, ניתן לחשוב על ערך הזרימה בתור כמות הזרימה שעוברת ברשת הזרימה ביחידת זמן.

יש לשים לב כי פונקציית הזרימה מגדירה את כמות הזרימה נטו שעוברת בין שני הצמתים. לדוגמה, זרימה בגודל 5 שעוברת מצומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} אל צומת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} אין פירושה בהכרח כי עוברות 5 יחידות של זרימה מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} - ייתכן למשל כי בפועל עוברות 12 יחידות מ-$\ u$ אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} , ועוברות 7 יחידות מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} , כך שהשינוי נטו בכמות החומר בשני הצמתים מתבטא בכך שעוברות 5 יחידות מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ u} אל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ v} . בשל כך, אותה פונקציית זרימה יכולה למדל מספר רב של זרימות שונות.

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

ערך מורחב – שיטת פורד פולקרסון

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

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

שיטת הרם-וקדם

שיטת הרם-וקדם (Push–relabel) מייצגת גישה שונה לפתרון בעיית זרימת המקסימום, שאינה דומה לשיטת פורד-פולקרסון. ניתן לממש אותה באופן יעיל כך שיתקבל אלגוריתם שזמן הריצה שלו הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(|V|^3)} - שיפור יחסי לזמני הריצה של מימושי שיטת פורד-פולקרסון עבור גרפים בעלי קשתות רבות.

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

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

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

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

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

מימוש זה מבטיח זמן ריצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(|V|^2\cdot|E|)} . כדי להבטיח זמן ריצה של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ O(|V|^3)} משכללים את דרך הבחירה של הצומת שעליו יבוצעו פעולות ההרם-וקדם, כך שהאלגוריתם מתמקד בכל פעם בצומת בודד ומרוקן אותו לחלוטין.

יישומים

גרפים דו צדדיים

שגיאה ביצירת תמונה ממוזערת:

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

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

בהינתן גרף דו צדדי המורכב משתי קבוצות צמתים $\ A,B$, כך שכל קשת היא בין צומת השייך ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ A} וצומת השייך ל-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ B} , בונים רשת זרימה כדלהלן: ראשית, מוסיפים צמתים חדשים שישמשו כמקור וכבור: הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s,t} . כעת, מחברים בקשתות את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ s} לכל צומתי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ A} , ואת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ t} לכל צומתי $\ B$. נותנים לכל הקשתות קיבולת 1. לא קשה להוכיח כי זרימת מקסימום ברשת זו משרה שידוך מקסימום בגרף המקורי, כאשר הקשתות שמשתתפות בשידוך הן אלו בהן עובר זרם.

לקריאה נוספת

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

קישורים חיצוניים

מדיה וקבצים בנושא רשת זרימה בוויקישיתוף

• רשת זרימה, באתר MathWorld (באנגלית)   

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

29680830רשת זרימה