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