הרעיון הבסיסי שמנחה את השיטה הוא זה: בתחילה, מזרימים מן המקור את כמות החומר המקסימלית האפשרית - כלומר, מרווים את כל הקשתות היוצאות ממנו. התוצאה אינה פונקציות זרימה חוקית, שכן זרימה נכנסת לשכניו של המקור אך אינה יוצאת מהן, ולכן לא מתקיים אילוץ הזרימה - לצמתים הללו ישנה "זרימה עודפת". האלגוריתם עובר על צמתים בעלי זרימה עודפת ומעביר מהן חלק מהזרימה הלאה (זהו ה-"קדם" שבשם השיטה, ובאנגלית Push), עד אשר היא מגיעה אל הבור או חוזרת אל המקור. ניתן להראות כי כאשר לא יהיה באף צומת עודף זרימה, כלומר תתקבל זרימה חוקית, יתקיימו גם תנאי משפט זרימה-מקסימלית חתך-מינימלי, ולכן הזרימה שתתקבל היא אופטימלית.
כדי להבטיח את עצירת האלגוריתם במהירות, לא מתירים העברת זרימה מכל צומת לשכן שלו, אלא מגדירים כלל נוסף, המבוסס על תכונת "גובה" של הצמתים. בגרף בעל n צמתים נותנים תחילה לכל הצמתים פרט למקור את הגובה 0, ולמקור נותנים גובה n. לאחר ההזרמה הראשונית מהמקור לשכניו, מתקיים הכלל הבא: מותר לצומת להזרים רק לצומת שקטן ממש ממנו (ניתן לדרוש אף שהפרשי הגבהים ביניהם יהיו בדיוק 1). כדי לאפשר שימוש בכלל זה מגדירים פעולה נוספת שאותה האלגוריתם מסוגל לבצע - הרמת צומת כך שיהיה גבוה מכל שכניו הרלוונטיים (זוהי פעולת ה"הרם" שבשם השיטה, ובאנגלית Lift או Relabel). הגובה נבחר בתור הגובה המינימלי הדרוש שעבורו הצומת יהיה גבוה מכל השכנים שעוד ניתן להזרים אליהם (כלומר, שהקשת אליהם אינה רוויה).
במימוש הנאיבי של שיטת הרם-וקדם, האלגוריתם הוא כדלהלן:
מימוש זה מבטיח זמן ריצה של formula_32. כדי להבטיח זמן ריצה של formula_31 משכללים את דרך הבחירה של הצומת שעליו יבוצעו פעולות ההרם-וקדם, כך שהאלגוריתם מתמקד בכל פעם בצומת בודד ומרוקן אותו לחלוטין.
יישומים.
גרפים דו צדדיים.
ניתן להשתמש ברשתות זרימה כדי למצוא שידוך מקסימום בגרף דו צדדי בזמן הדרוש לריצת אלגוריתם למציאת זרימת מקסימום.
בהינתן גרף דו צדדי המורכב משתי קבוצות צמתים formula_34, כך שכל קשת היא בין צומת השייך ל-formula_35 וצומת השייך ל-formula_36, בונים רשת זרימה כדלהלן: ראשית, מוסיפים צמתים חדשים שישמשו כמקור וכבור: formula_37. כעת, מחברים בקשתות את formula_38 לכל צומתי formula_35, ואת formula_40 לכל צומתי formula_36. נותנים לכל הקשתות קיבולת 1. לא קשה להוכיח כי זרימת מקסימום ברשת זו משרה שידוך מקסימום בגרף המקורי, כאשר הקשתות שמשתתפות בשידוך הן אלו בהן עובר זרם.
מורפיקס
אתר מורפיקס הוא מילון עברי־אנגלי ואנגלי־עברי ומנוע חיפוש מקוון.
היסטוריה.
יוצרת ומפעילת מורפיקס היא מלינגו, חברת בת של אנציקלופדיה בריטניקה.
בנובמבר 2009 הושק שיתוף פעולה בין מורפיקס ואתר mako, במסגרתו קשת, מפעילת מאקו, מנהלת את הפן הכלכלי ומורפיקס תנהל את הפן התוכני ותרחיבו. בעת השקת שיתוף הפעולה דיווחה מורפיקס כי לשירות למעלה מ-100 אלף משתמשים ייחודיים מדי יום.
ביוני 2011 יצאה אפליקציית מורפיקס לאנדרואיד. אפליקציה לאייפון הייתה קיימת כבר מינואר 2010 ובעת השקת האפליקציה לאנדרואיד היו לה כ-150 אלף הורדות.
במרץ 2012 הוציאה ynet בשיתוף פעולה עם מורפיקס אפליקציה ייעודית לפתרון תשבצים.
חברת פרולוג הוציאה בשיתוף עם מורפיקס עשר אפליקציות מילון, בין עברית למגוון שפות.
טיפול בהטיות.
בין יתרונותיו של מורפיקס יש לציין את הגמישות הלשונית שלו, שבזכותה ניתן לרשום מילה בהטיה מסוימת שלה, ולקבל תרגום לצורה היסודית שלה (במילון), או לקבל תוצאות חיפוש בכל הטיותיה.
מרבית מנועי החיפוש מוצאים מילים בדיוק בצורה שנרשמו. אופן פעולה זה מהווה בעיה מבחינת המחפש, משום שלמילים רבות ישנן צורות כתיב שונות, למשל עקב כתיב מלא וכתיב חסר, ולעיתים תופיע מילה דווקא בהטיה מסוימת, או בצירוף אותיות השימוש, ולא בצורתה הבסיסית. על־מנת להיות משוכנע שמצא את כל שברצונו למצוא, ייאלץ המחפש לערוך חיפושים אחדים. בעיה זו מחריפה יותר בעת חיפוש במילון, שבו, בטכניקה הרגילה, על המחפש להיות בעל שליטה מעולה בדקדוק, כדי להעביר את המילה שהוא מחפש לצורה הבסיסית שלה, שהיא הצורה היחידה המופיעה במילון. באנגלית בעיה זו פחות חמורה, אך גם בשפה זו לא תמיד קל לעבור מצורת הרבים לצורת היחיד. חיפוש המילה children במורפיקס מחזיר את התוצאה child, כנדרש. המעבר בין צורות הפועל השונות אינו פשוט אף הוא, ונדרשת היכרות טובה עם השפה כדי לעבור מ־wrote או written ל־write.
דוד רביבו
דוד רביבו (נולד ב-5 בדצמבר 1977) הוא כדורגלן עבר ישראלי וכיום מאמן הפועל אדומים אשדוד.
רביבו הוכתר לשיאן הבישולים של ליגת העל שלוש פעמים (2005/2006, 2008/2009, 2011/2012), והוא שיאן הבישולים בכל הזמנים עם 107 בישולים.
קריירה.
רביבו נולד וגדל באשדוד, החל את דרכו במחלקת הנוער של מכבי עירוני אשדוד וכרטיסו נרכש בשנת 1995 על ידי קבוצת מכבי תל אביב. בעונת 1996/1997 עלה לקבוצת הבוגרים של המועדון, ובמשחקו הראשון שיחק נגד מכבי חיפה. בעונת 1998/1999 זכה עם הקבוצה בגביע הטוטו.
בתחילת עונת 2000/2001 עבר רביבו למועדון ספורט אשדוד, בה שיחק במשך תשע עונות רצופות. ב-2006 ניסה מזלו בלוס אנג'לס גלאקסי, אך בשל פיטורי מאמנה נאלץ לחזור לאשדוד. בקיץ 2009 עבר להפועל באר שבע, ולאחר שנתיים חזר לאשדוד.
לקראת עונת 2013/2014 חתם רביבו בקבוצת בית"ר ירושלים. ב-27 בינואר 2014, אחרי שלא קיבל דקות משחק רבות בבית"ר ירושלים, שוחרר מהקבוצה אחרי חצי שנה. ב-28 בינואר 2014 חתם רביבו בהפועל חיפה. ב-12 ביוני 2014 חתם רביבו במכבי יבנה מהליגה הלאומית.
ב-3 ביולי 2016 הודיע רביבו על פרישה ממשחק פעיל ומונה לעוזר מאמן הפועל בני לוד מהליגה הלאומית. עם תחילת העונה חזר בו מהפרישה והחל גם לשחק בקבוצה. ב-19 בדצמבר 2016 חתם רביבו בהפועל מרמורק מליגה א', עמה העפיל לליגה הלאומית בתום העונה. רביבו שימש כעוזרו של ניסן יחזקאל, מאמן הקבוצה, ובמקביל ב-11 ביולי 2017 חתם בהפועל בני אשדוד מליגה ג', במדיה ערך הופעה אחת בגביע וכבש שער אחד. ב-1 באוקטובר 2017 חתם בהפועל אדומים אשדוד מליגה ב', ובתום העונה העפיל עמה לליגה א'.
ב-4 ביולי 2019 רביבו חתם בקבוצת עירוני בית דגן מליגה ב', במדיה ערך שבע הופעות. ב-22 באוקטובר 2019 חתם במכבי השקמה/רמת חן מליגה ג'.
נבחרת ישראל.
לזכותו של רביבו שער אחד בארבע הופעות במדי הנבחרת הצעירה של ישראל. הופעת הבכורה שלו בנבחרת הבוגרת הייתה במוקדמות מונדיאל 2006 במשחק מול נבחרת קפריסין, ובסך הכל הופיע בשלושה משחקים במדי הנבחרת.
מחוץ למגרש.
רביבו גרוש ואב לשניים. אחיו הגדולים הם כדורגלני העבר חיים רביבו ואלי רביבו, אחיו הצעיר הוא הכדורגלן שי רביבו ובן דודו הוא הכדורגלן אמיר לביא.
בשנת 2018 הצטרף רביבו לעונה השישית של תוכנית המציאות גולסטאר. בשנת 2020 שב להשתתף בתוכנית המציאות גולסטאר בעונת האולסטאר בברזיל כחלק משחקני החיזוק בגמר העונה.
ב-6 ביולי 2022 מונה לעוזר מאמן הפועל אדומים אשדוד. אך לאחר פיטורי חיים לוי מונה למאמן הקבוצה.
משפט זרימה מקסימלית - חתך מינימלי
בתורת הגרפים, משפט זרימה מקסימלית - חתך מינימלי (Max-flow min-cut) עוסק בזרימה המקסימלית שניתן להעביר ברשת זרימה. המשפט קובע כי כמות הזרימה המקסימלית שניתן להעביר ברשת זרימה שווה לקיבולת המקסימלית של החתך עם הקיבולת המינימלית ברשת.
המשפט הוא מקרה פרטי של הדואליות של תכנון ליניארי ומכליל את משפט מנגר הקובע כי גרף הוא k-קשיר אם ורק אם בין כל שני קודקודים בגרף קיימים k מסלולים זרים בקודקודים והוא k-קשיר-קשתות אם ורק אם בין כל שני קודקודים בגרף קיימים k מסלולים זרים בקשתות.
תיאור פורמלי.
רשת זרימה מורכבת מגרף formula_1, משני צמתים מיוחדים - המקור (Source) formula_2 והבור (Sink) formula_3, ומפונקציית קיבול formula_4 שמתאימה לכל זוג צמתים את כמות הזרימה המקסימלית שיכולה לעבור מהראשון שבהם אל השני (ויכולה להיות אינסופית, כלומר ללא הגבלה). אם לא קיימת קשת מ-formula_5 אל formula_6, מניחים כי formula_7.
בהינתן רשת זרימה formula_1 עם פונקציית קיבול formula_9, חתך ברשת הזרימה הוא חלוקה של צומתי הרשת לשתי קבוצות זרות formula_10 כך שאחת מהן מכילה את המקור והשנייה את הבור: formula_11.
קיבול של חתך מוגדר באמצעות סכום הקיבולות של הקשתות המצביעות מצומת בקבוצה formula_12 לצומת בקבוצה formula_13 (יש לשים לב שההגדרה אי-סימטרית):
חתך מינימלי של רשת זרימה הוא חתך כזה שהקיבולת שלו מינימלית מבין כל החתכים של הרשת. קיבולת החתך היא סכום הקיבולות של הקשתות החוצות את החתך.
פונקציית זרימה formula_15 מתאימה לכל זוג צמתים formula_16 את כמות הזרימה מ-formula_5 אל formula_6 (לכיוון יש חשיבות), כך שמתקיימים התנאים הבאים:
הערך של זרימה היא הזרימה נטו שיוצאת מן המקור, כלומר formula_23.
עבור רשת זרימה formula_1 עם פונקציית קיבול formula_9 וזרימה חוקית formula_15 הגרף השיורי הוא רשת זרימה עם אותה קבוצת צמתים וקשתות כך שהקיבול של קשת (u,v) הוא formula_27.
משפט זרימה מקסימלית - חתך מינימלי אומר כי שלושת התנאים הבאים שקולים, עבור זרימה formula_28:
הוכחה.
ראשית, אם formula_28 היא זרימה מקסימלית, והגרף השיורי של רשת הזרימה עבור formula_28 כן מכיל מסלולי שיפור, אז ניתן להגדיל את formula_28 על ידי העברת זרימה נוספת באחד ממסלולי השיפור, בסתירה למקסימליות formula_28. לכן 1 גורר את 2.