|
|
עמוד:193
עתה נתבונן בגרף שלהלן י מטריצת הסמיכות המתאימה לגרף זה היא נחשב : אם ברצוננו לדעת אם קיים מסלול באורך של לכל היותר 2 בין שני קדקודים כלשהם בגרף , אזי נמצא אותו בעזרת חיבור בוליאני של מטריצות . A [ ij ] = 1 אם ורק אם קיים מסלול באורך 1 מהקדקוד / לקדקוד J כמו כן , A [ ij ] - 1 אם ורק אם קיים מסלול באורך 2 בדיוק מהקדקוד י לקדקוד j אך = 1 נ ' . / י ] Af 4 yj + ^ אם ורק אם קיים מסלול באורך 1 או שקיים מסלול באורך , 2 י כלומר אם קיים מסלול באורך של לכל היותר . 2
|
|