|
|
صفحة: 358
שאלה 6 . 9 הפעילו את האלגוריתם של פרים ( Prim ) על הגרפים שבשאלה . 6 . 8 שאלה 6 . 10 נתון גרף לא מכוון , G = ( V , E ) ונתונה פונקציית המשקל . W : £ - > /? כל קשת בגרף צבועה בשחור או בלבן . בהינתן עץ פורש , 7 נסמן m -1 את מספר קשתותיו השחורות , וב- מ ; את 2 x מספר קשתותיו הלבנות . המטרה היא למצוא , מבין העצים הפורשים המינימליים , את העץ שעבורו \ m - " ! | מקסימלי . א . תארו אלגוריתם יעיל ככל שתוכלו לבעיה . ב . מה סיבוביות זמן הריצה של האלגוריתם ? הסבירו את תשובתכם .
|
|