עמוד:227

ואורך המסלול המינימלי מהקדקוד A לקדקוד D הוא , 7 והמסלול הוא A—^ C ^ - ^ B—^ D ברשת הבאה נתבונן במסלול המודגש , שהוא המסלול בעל האורך המינימלי מהקדקוד A לקדקוד D קל לראות כי במסלול זה מספר הקשתות הנכנסות לקדקוד , C הוא 1 ( הקשת . (( AQ מספר הקשתות היוצאות מהקדקוד , C הוא גם כן 1 ( הקשת . {( CB ) באופן אנלוגי , מספר הקשתות הנכנסות והיוצאות מהקדקוד , B שדרכן עוברת הדרך הקצרה ביותר מהקדקוד A לקדקוד , D שווה י קשת אחת נכנסת ( C , B ) וקשת אחת יוצאת . ( £ , £ >) מסקנה : עבור כל קדקוד u במסלול הקצר ביותר , פרט לקדקוד המקור , 4 ולקדקוד היעד , D מתקיים שמספר הקשתות היוצאות מהקדקוד u שווה למספר הקשתות הנכנסות לקדקוד , « שדרכן עוברת הדרך הקצרה מקדקוד המקור A לקדקוד היעד D ( קשת אחת נכנסת וקשת אחת יוצאת . ( לכן , נגדיר את המשתנים הבאים : לכל קשת !(/ , . /) m ON p uw rmpn n T 1 1 (/ , . /) Twp T a = אם הדרך הקצרה אינה עוברת דרך קשת זדו ג [ °

מטח : המרכז לטכנולוגיה חינוכית


לצפייה מיטבית ורציפה בכותר