|
|
עמוד:186
שאלה 4 . 21 נתון גרף מכוון G = ( V , E ) המיוצג באמצעות רשימות סמיכות . א . כתבו אלגוריתם , בעל סיבוביות זמן ריצה , 0 (\ E \ + | V |) המחשב את דרגת היציאה של כל קדקוד . ב . כתבו אלגוריתם המחשב את דרגת הכניסה של כל קדקוד . ג . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם בסעיף . 'ב נמקו את תשובתכם . שאלה 4 . 22 נתון ו המטריצה המוחלפת ( transpose ) של מטריצה A מסומנת כ- A ומוגדרת כך י השורה הראשונה של rr > r \ r \ A העמודה הראשונה של 7 " ^ השורה השנייה של A תהיה העמודה השנייה של . A השורה השלישית של A תהיה העמודה השלישית של , A וכדומה . לדוגמה : עבור המטריצה הזאת : המטריצה המוחלפת היא ו א . נתון גרף לא מכוון , G המיוצג באמצעות מטריצת סמיכות . A האם A = A תמיד ? נמקו את תשובתכם . ב . נתון גרף מכוון , G המיוצג באמצעות מטריצת סמיכות . ^ האם A = A תמיד ? נמקו את תשובתכם .
|
|