|
|
עמוד:185
שאלה 4 . 18 א . נתון גרף לא מכוון ? . G = ( V , E ) . 1 יצגו את הגרף G באמצעות רשימות סמיכות . . 2 חשבו את סכום האורכים של כל רשימות הסמיכות , . 3 מהו הקשר בין התוצאה שקיבלתם בסעיף הקודם לבין מספר הקשתות שבגרף ? G ב . בנו גרף מכוון עם 4 צמתים . . 1 הראו את הייצוג של הגרף G באמצעות רשימות סמיכות . . 2 חשבו את סכום האורכים של כל רשימות הסמיכות . . 3 מהו הקשר בין התוצאה שקיבלתם בסעיף הקודם לבין מספר הקשתות שבגרף ? G שאלה 4 . 19 נתון הגרף G אשר מיוצג באמצעות רשימות סמיכות . א . אם הגרף G הוא גרף מכוון , מהו סכום האורכים של כל רשימות הסמיכות ? נמקו את תשובתכם . ב . אם הגרף G הוא גרף לא מכוון , מהו סכום האורכים של כל רשימות הסמיכות ? ג . הראו כי כמות הזיכרון הדרושה לייצוג גרף G באמצעות רשימות סמיכות היא : O ( max (| V | , | £ |)) = 0 (| V | + | £ |) שאלה 4 . 20 מהי כמות הזיכרון הדרושה לייצוג גרף G באמצעות מטריצת סמיכות ? נמקו את תשובתכם .
|
|