|
|
עמוד:210
פתרון לשאלה 4 . 12 הדרך הטבעית להצגה של גרף היא מערך דו-ממדי מסדר . nxn נכנה אותו . g מערך דו-ממדי ( מטריצה ריבועית ) מייצג כל זוג אפשרי של צמתים שניתן להעביר ביניהם קשת . פתרון לשאלה 4 . 13 מבנה הנתונים במקרה הזה יהיה גם מערך דו-ממדי ( מטריצה ריבועית ) מסדר . nxn פתרון לשאלה 4 . 15 כידוע , עבור גרף המכיל n צמתים יישמרו « מקומות לקשתות , כאשר אנו מייצגים את הגרף בעזרת מטריצת סמיכות . אף-על-פי שאנו יודעים מראש מהו מספר הצמתים בגרף , איננו יודעים מראש מאומה על מספר הקשתות שבו . אם לגרף מעט מאוד קשתות , אזי מטריצת הסמיכות ( במקרה של גרף משוקלל גם מטריצת סמיכות עם משקולות ) תהיה דלילה . כדי למנוע בזבוז מקום , נשתמש במערך של רשימות כמתואר לעיל .
|
|