|
|
صفحة: 322
שאלה 5 . 42 נתון גרף מכוון . הסגור הרפלקסיבי-טרנזיטיבי של G הוא גרף G * שמכיל קשת , (« > v ) אם ורק אם G-2 יש מסלול מכוון ( של אפס קדקודים או יותר ) . v- \> u-a אפשר לנסח זאת במונחים של מטריצת הסמיכות של G * כדלקמן מטריצת הסגור C היא מטריצה בוליאנית שבה C [ u , v ] = 1 אם v נגיש . G-1 « -מ בהינתן מטריצת סמיכות , G IUV A ברצוננו לחשב את מטריצת הסגור . C ציינו את היתרונות ואת החסרונות של שתי השיטות ( שיטת BFS והאלגוריתם של פלוידוורשל . ( שאלה 5 . 45 לפניכם רשת ? . א . מצאו את המסלולים הקצרים ביותר מן הצומת 1 לכל אחד מן הצמתים האחרים ברשת הנתונה , לפי אלגוריתם דיקסטרה . ב . מצאו את המסלולים הקצרים ביותר מכל קדקוד לכל קדקוד אחר ברשת הנתונה לפי אלגוריתם פלויד-וורשל . ג . מצאו מסלולים מינימליים מכל צומת לכל צומת על-ידי אלגוריתם פלויד-וורשל .
|
|