|
|
עמוד:225
קל לראות שברשת הזאת קייס מסלול מעגלי שאורכו שלילי , למשל מהקדקוד 2 לקדקוד 3 וחזרה לעצמו . קל לראות שברשת הזאת לא קיים מסלול שהוא המינימלי ( סופי ) מקדקוד 1 לקדקוד . 2 אורך המסלול הפשוט מקדקוד 1 2-ל הנו . 2 אך עבור המסלול הזה ו אורך המסלול מקדקוד 1 לקדקוד 2 הוא -1 ועבור המסלול הזה : אורך המסלול מקדקוד 1 לקדקוד 2 הוא , ( -4 ) וככל שעוברים מספר רב יותר של פעמים במעגל מקדקוד 2 לקדקוד , 2 אזי אורך המסלול מקדקוד 1 לקדקוד 2 קטן יותר , ועבור מסלול כלשהו , שהוא סדרה אינסופית של קדקודים , אורך המסלול שואף . ( -00-ל לפיכך , ניתן להסיק , שלא קיים מסלול שהוא סדרה סופית של קדקודים בגרף , אשר בעזרתו ניתן יהיה לקבוע מהו אורך המסלול המינימלי מקדקוד 1 לקדקוד . 2 מכאן נסיק כי ברשת שבה אין מעגלים בעלי אורך אי-חיובי קיים מסלול מינימלי .
|
|