|
|
עמוד:224
ודאו שמסלולים אלה הם הקצרים ביותר , ובדקו שלא קיים מסלול קצר יותר מהקדקוד A לקדקוד . D מסקגה : יכולים להיות מספר מסלולים קצרים בין שני קדקודים בגרף . תזכורת : מסלול כלשהו : Off סדרה סופית של k קדקודים ברשת , כאשר לכל 0 < i < k- \ קדקוד V + 1 סמוך ' לקדקוד Vj בגרף . כלומר קיימת קשת , ( V ' -, , V ) והמשקל של הקשת , , ' ccr , H' ( V יכול להיות חיובי , אפס או שלילי . שאלה 5 . 7 מה המשמעות של משקל שלילי על קשת כלשהי בגרף ? הביאו דוגמה . המשקל של המסלול המעגלי p = ( V-, , ..., V ) מסומן . " & QV ומוגדר כסכום המשקלות המיוחסות לקשתות בגרף המהוות מעגל באורך 2 מהקדקוד V ? לעצמו . בתרשים משורטטת רשת ( גרף משוקלל ) שימו לב לכך שברשת הזאת קיים מעגל שאורכו , 0 למשל , מקדקוד 2 3-ל וחזרה לעצמו . ברור שברשת הזאת אין פתרון יחיד לאורך המסלול המינימלי מהקדקוד 1 לקדקוד , 3 מאחר שברשת קיים מסלול מעגלי שאורכו . 0 דוגמה למסלול כזה . 1 - > 2 - > 3 - » 2 - > 3 - > 2 - > 3 וזאת אינה סדרה סופית . לעומת זאת , אם נתבונן בתרשים שלהלן
|
|