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