|
|
صفحة: 226
את התכונה הזאת נוכיח בהמשך . מאחר שאורך המסלול המעגלי חייב להיות חיובי , אזי אורך המסלול שלהלן ו , V V . Vi Vi JV אשר כולל מעגל מהקדקוד / לעצמו V V i V t v k גדול יותר מאורך המסלול v v v v אשר לא כולל מעגלים . o l t k לאור זאת נסיק כי : אם ק"ם מסלול שהוא הקצר ביותר ברשת , אזי המסלול חייב להיות מסלול פשוט , כלומר מסלול שבו אף קשת של הגרף אינה מופיעה יותר מפעם אחת . נתבונן ברשת הבאה ו אף-על-פי שעדין לא למדנו אלגוריתמים למציאת מסלולים בעלי אורך מינימלי , קל לראות כי : אורך המסלול המינימלי מהקדקוד A לקדקוד C הוא , 4 והמסלול הוא אורך המסלול המינימלי מהקדקוד A לקדקוד B הוא , 6 והמסלול הוא A—^ C—^> B אורך המסלול המינימלי מהקדקוד A לקדקוד E הוא , 5 והמסלול הוא A ^ - ^ C—^ E
|
|