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

נתון גרף לא-מכוון וקשיר $\displaystyle G=(V,E)$ , וכן טבלת עלויות על הקשתות Edge-Costs. בגרף יש מעגל, כלומר מסלול (פשוט) שמתחיל ומסתיים באותו צומת. ידוע שקיימת קשת $\displaystyle e\in E$ כלשהי כך שEdge-Costs[e] > Edge-Costs[e'] לכל קשת $\displaystyle E\ni e'\neq e$ במעגל. במילים אחרות, $\displaystyle e$ היא הקשת היקרה ביותר (ממש) במעגל.