נתאר את בעיית האופטימיזציה הבאה: קלט: גרף (פשוט) מכוון G = (V, E). פלט: קבוצת קשתות E' E גדולה ככל האפשר, כך ש…

נתאר את בעיית האופטימיזציה הבאה: קלט: גרף (פשוט) מכוון $G = (V, E)$. פלט: קבוצת קשתות $E' \subseteq E$ גדולה ככל האפשר, כך שהגרף $G' = (V, E')$ חסר מעגלים. נתבונן באלגוריתם הקירוב הבא לבעיה: קלט: $G = (V, E)$ – גרף מכוון. 1. נמצא את כל הקשתות $(i, j) \in E$ המקיימות $i < j$. נסמן קבוצה זו ב-$E_1$. 2. נמצא את כל הקשתות $(i, j) \in E$ המקיימות $j < i$. נסמן קבוצה זו ב-$E_2$. 3. נחזיר את הקבוצה הגדולה יותר מבין $E_1, E_2$ (אם הן באותו גודל, נחזיר את $E_1$). מהו יחס הקירוב של האלגוריתם ? הוכיחו תשובתכם.