עמוד:194

בדומה לשאלה הקודמת , אם ברצוננו לדעת אם קיים מסלול באורך של 3 לכל היותר בין שני קדקודים בגרף , אזי נמצא אותו בעזרת חיבור בוליאני של מטריצות , A = A + A + A 3 כלומר , קיים מסלול באורך 3 או פחות אם קיים מסלול באורך 1 או באורך 2 בדיוק או באורך 3 בדיוק . העיה : ייתכן שיהיה מסלול באורך 1 וגם באורך 2 וגם באורך . 3 כיוון שהחיבור הוא בוליאני , אזי טענה : נתון הגרף G = ( V , E ) כאשר רו n ) \ V \ = קדקודים בגרף . ( אם קיים מ 0 לול באורך m מהקדקוד / לקדקוד / כאשר , m > n אז תמיד נוכל למצוא מסלול ארור מהקדקוד ו לקדקוד j באורך של לכל היותר ח . תהליך מציאת המסלול הקצר ביותר trrt בגרף | v | = n , G קדקודים , ואורך המסלול / -מ . / -ל הנו , «? ומתקיים , m > n אז לפחות קדקוד אחד u מופיע במסלול פעמיים . כלומר , קיים מסלול מהקדקוד / לקדקוד . u בנוסף , קיים מסלול מעגלי מהקדקוד » לקדקוד , « וקיים מסלול מהקדקוד u לקדקוד . / כמתואר באיור להלן : אס נסיר את המסלול המעגלי מהצומת u לצומת , « אזי עדיין קיים מסלול / -מ . / -ל נחזור על התהליך הזה עד שנגיע למסלול ; -מ 1 / -ל המכיל כל צומת בגרף לכל היותר פעם אחת . לכן , אורכו של המסלול מכל קדקוד / לכל קדקוד j הוא לכל היותר . «

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


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