|
|
עמוד:187
שאלה 4 . 23 נתון הגרף המכוון . G ( V , E ) הגרף המוחלף של G מסומן ומוגדר כ , GT = ( V , not כאשר בקבוצת הקשתות E נמצאות אותן הקשתות £ -שב אבל כיווניהן הפוכים . כלומר , אם , (« , v ) s £ אזי . (« , v ) sE למשל , עבור הגרף G שמתואר להלן : הגרף המוחלף G הוא כדלקמן : א . אם הגרף מיוצג באמצעות מטריצת סמיכות , . 1 תארו אלגוריתם לחישוב . G 2 . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם בסעיף ? 1 ב . אס הגרף מיוצג באמצעות רשימות סמיכות , . 1 תארו אלגוריתם לחישוב . G 2 . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם בסעיף ? 1 שאלה 4 . 24 נתון הגרף . K מצאו את המטריצה , A כאשר A מייצגת מטריצת סמיכות . תנו 5 משמעות לאברי המטריצה . A
|
|