|
|
עמוד:176
להלן אלגוריתם לבניית הגרף : צור מטריצה G של אפסים מסדר . « x « כל עוד קיים קלט , בצע : קלוט זוג צמתים ( a , b ) בצע : G [« p ] = 1 סוף הלולאה . 4 . 3 . 3 ייצוג רשת באמצעות מטריצה ריבועית השיטה השנייה לייצוג גרף שנכיר משמשת גם לייצוג גרף משוקלל ( בעל משקל לקשתות , ( כלומר לייצוג רשת . השיטה הזאת משתמשת במטריצה ריבועית . מאחר שמספר הצמתים בגרף ידוע מראש ( נניח , (« אזי כל צומת בגרף מיוצג על-ידי מספר שלם בין 0 ל- . (^! -1 ) בשיטה הזאת נניח שאין כל מידע המיוחס לצמתים . כמו כן , נרצה לדעת אם קיימות קשתות עבור הגרף , וגם את המידע המיוחס להן ( בשיטה הזאת ניתן לייחס תכונה אחת בלבד לכל קשת . ( לאור זאת , הדרך הטבעית להצגה של גרף היא מערך דו-ממדי ( מטריצה ריבועית ) מסדר . // x n הנקרא מטריצת המשקלות . נסמן אותה ב . <> מערך דו-ממדי מייצג כל זוג סדור אפשרי של צמתים . לגבי כל אלמנט במטריצה זו נשמור מספר מאפיינים ; א . האם קיימת קשת בין זוג סדור של צמתים . ב . אם קיימת קשת בין זוג סדור של צמתים , נרצה לדעת מהו המידע המיוחס לה . לדוגמה , נתון הגרף המכוון הזה ! נייצג את הגרף בעזרת המטריצה הריבועית שלהלן ו
|
|