|
|
עמוד:361
א . כתבו אלגוריתם יעיל ככל האפשר , המוצא בגרף עץ פורש בעל מספר מרבי של קשתות לבנות . ב . מהי סיבוביות זמן הריצה של האלגוריתם שהצעתם ? שאלה 6 . 19 נתון גרף לא מכוון G = ( V , E ) עם פונקציית משקל על הקשתות , וידוע שכל המשקלות על הקשתות שונים זה מזה . הוכיחו שקיים עץ פורש מינימלי יחיד בגרף . שאלה 6 . 20 נתון גרף G = ( V , E ) לא מכוון , קשיר , עם פונקציית המשקל . W-. E ^ ? { 1 , 2 , ..., 9 , 10 ) ; תארו אלגוריתם עם סיבוביות זמן ריצה של O (\ E \) למציאת עץ פורש מינימלי עבור הגרף G שאלה 6 . 21 להלן אלגוריתם למציאת עץ פורש מינימלי עבור הגרף הנתון . G = ( V , E ) צעד : 1 מיין את הקשתות { E ) בסדר יורד , מהקשת בעלת המשקל המקסימלי עד לקשת בעלת המשקל המינימלי . : 2 צעד ^> -A ) A < -G צעד 13 לפי הסדר היורד שנקבע בצעד , 1 בדוק לכל קשת אם היא נמצאת על מעגל פשוט בגרף A אם כן , קבעו A <^ A - { e } א . הוכיחו בסיום האלגוריתם כי A הוא עץ פורש מינימלי . ב . מה סיבוביות זמן הריצה של האלגוריתם הנתון ? שאלה 6 . 22 נתון גרף G = ( V , E ) לא מכוון , קשיר , ועם פונקציית המשקל :
|
|