מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמים למציאת עפ"מ/תרגילים/קבוצת היזון חוזר/שאלה

נתון גרף לא-מכוון וקשיר , וכן טבלת עלויות על הקשתות Edge-Costs.


הגדרה:

קבוצת קשתות היא קבוצת קשתות היזון חוזר אם לאחר הסרתה, חסר מעגלים; במילים אחרות, הקבוצה היא קבוצת קשתות היזון חוזר אם הוא יער.


בשאלה זו הינך מתבקש למצוא אלגוריתם יעיל המקבל גרף ומחזיר קבוצת היזון חוזר זולה ככל האפשר.


רמז

אל תתמקד בקבוצה , אלא בקבוצה המשלימה אותה, . אם היא קבוצת קשתות ההיזון החוזר הזולה ביותר - מהי ?‏ אם היא קבוצת קשתות ההיזון החוזר הזולה ביותר - איך תוכל למצוא את הקבוצה המשלימה לה ביעילות?