הבדלים בין גרסאות בדף "רשת זרימה"

הוסרו 210 בתים ,  לפני שנה
←‏יישומים: תיקון טעות: במקרה הכללי של matching הבעיה אינה NP שלמה. השקילות בין כיסוי צמתים מינימלי לmatching נכונה לגרפים דו- צדדים (משפט קוניג).
מ (הוספת תבנית:MathWorld בקישורים חיצוניים (תג) (דיון))
(←‏יישומים: תיקון טעות: במקרה הכללי של matching הבעיה אינה NP שלמה. השקילות בין כיסוי צמתים מינימלי לmatching נכונה לגרפים דו- צדדים (משפט קוניג).)
===גרפים דו צדדיים===
[[קובץ:Matching_With_Flow.png|שמאל|מסגרת|100px|דוגמה לרשת זרימה שמתקבלת לאחר הבניה]]
ניתן להשתמש ברשתות זרימה כדי למצוא [[שידוך מקסימום]] ב[[גרף דו צדדי]] בזמן הדרוש לריצת אלגוריתם למציאת זרימת מקסימום (לחלופין, מכיוון ששידוך מקסימום משרה [[כיסוי בצמתים]] מינימלי, ניתן למצוא כיסוי שכזה - במקרה הכללי הבעיה היא [[NP-שלמה]]).
 
בהינתן גרף דו צדדי המורכב משתי קבוצות צמתים <math>\ A,B</math>, כך שכל קשת היא בין צומת השייך ל-<math>\ A</math> וצומת השייך ל-<math>\ B</math>, בונים רשת זרימה כדלהלן: ראשית, מוסיפים צמתים חדשים שישמשו כמקור וכבור: <math>\ s,t</math>. כעת, מחברים בקשתות את <math>\ s</math> לכל צומתי <math>\ A</math>, ואת <math>\ t</math> לכל צומתי <math>\ B</math>. נותנים לכל הקשתות קיבולת 1. לא קשה להוכיח כי זרימת מקסימום ברשת זו משרה שידוך מקסימום בגרף המקורי, כאשר הקשתות שמשתתפות בשידוך הן אלו בהן עובר זרם.