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

נתון גרף לא-מכוון וקשיר $\displaystyle G=(V,E)$, וכן טבלת עלויות על הקשתות Edge-Costs.

הגדרה: קבוצת קשתות $\displaystyle E'\subseteq E$ היא קבוצת קשתות היזון חוזר אם לאחר הסרתה, $\displaystyle G$ חסר מעגלים; במילים אחרות, הקבוצה היא קבוצת קשתות היזון חוזר אם $\displaystyle G'=(V,E\ E')$ הוא יער.

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

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