|
עמוד:191
לאור מה שהראינו קודם , עבור הגרף הנתון , G המיוצג על-ידי המטריצה A 2 , A היא מטריצת מסלולים באורך 2 מכל קדקוד בגרף לכל קדקוד אחר בגרף . מאחר ש : A [ a , b ] = 1 אז קיים מסלול באורך 2 מהקדקוד , c ^ a , A [ a , e ] = 1 אז קיים מסלול באורך 2 מהקדקוד a , -ל , A 2 [ a , d ] = 0 אז לא קיים מסלול באורך 2 מהקדקוד a -ל וכדומה . שימו לב , מהקדקוד a לקדקוד d קייס מסלול באורך 1 ( ראה במטריצה A את , lA [ a , d ] אך לא קיים מסלול באורך 2 ( ראה במטריצה , 4 את . { A 2 [ a , d ] בנוסף , נתבונן במסלולים מהקדקוד a לקדקוד x אין מסלול באורך 1 ( כי , ( A [ a , c ] = 0 אך קיים מסלול באורך 2 ( כי . { A 2 [ a , c ] = 1 מסקנה : " , 7 A 2 מטריצת מסלולים באורך , 2 עבור הגרף הנתון מכל קדקוד לכל קדקוד אחר בגרף . כלומר , הערך של A [ 1 \ j ] הוא ( TRUE ) 1 אם ורק אם קיים מסלול באורך 2 מהקדקוד / לקדקוד / בגרף . באופן דומה , אם נתבונן במטריצות A -j , A ונסתכל על אברי השורה a ( הראשונה ) במטריצה A ועל אברי העמודה d ( הרביעית ) במטריצה ונכפיל את שני הווקטורים ^ הבוליאניים ( כפל סקלרי ) נוכל לראות כי קיים מסלול ( לא פשוט ) באורך 3 מהקדקוד a לקדקוד 4 העובר דרך , a לא קיים מסלול באורך 3 מהקדקוד a לקדקוד 4 העובר דרך , b קיים מסלול באורך 3 מהקדקוד a לקדקוד 4 העובר דרך , c לא קיים מסלול באורך 3 מהקדקוד a לקדקוד 4 העובר דרך 4 ולא קיים מסלול באורך 3 מהקדקוד a לקדקוד 4 העובר דרך e תוצאת הכפל הסקלרי היא DN , ( TRUE ) 1 ורק אם קיים מסלול באורך 3 מהקדקוד a לקדקוד d דרך הקדקודים a או b או c או d או . e
|
|